给定一个包含 $N$ 个顶点和 $M$ 条边的无向简单连通图。

图的顶点编号为从 $1$ 到 $N$ 的连续整数，边编号为从 $1$ 到 $M$ 的连续整数。边 $i$ 连接顶点 $u_i$ 和 $v_i$。

该图具有以下特殊性质：对于每一条边 $i$ ($1 \le i \le M$)，都存在一条连接 $u_i$ 和 $v_i$ 且不包含该边的路径。我们将这样的路径称为边 $i$ 的“旁路”（bypass path）。同一条边可能存在多条旁路。

我们将使用 $1$ 到 $M$ 的连续整数作为颜色对边进行染色，每条边恰好分配一种颜色。某些颜色可能不被使用，某些颜色可能被多次使用。

如果染色满足以下性质，则称该染色是“有趣的”（interesting）：

• 如果两条边有公共顶点，则它们的颜色不同。
• 对于每一条边，都存在一条“特殊旁路”：该旁路所包含的边使用的颜色种类不超过 $8$ 种。

你的任务是找到一种有趣的染色方案，并对于 $M$ 条边中的每一条，输出一组可用于构建该边特殊旁路的颜色集合。

可以证明，在上述约束条件下，至少存在一种有趣的染色方案。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($3 \le N \le 5555, 3 \le M \le \min(N(N - 1)/2, 9999)$)。

接下来的 $M$ 行中，第 $i$ 行描述第 $i$ 条边，包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i < v_i \le N$)。

你可以假设每对 $(u, v)$ 在列表中最多出现一次，给定的图是连通的，并且在移除任意一条边 $(u, v)$ 后，仍然存在连接 $u$ 和 $v$ 的旁路。

输出格式

按以下格式输出任意一种有趣的染色方案。

第一行输出 $M$ 个整数。其中第 $i$ 个整数 $C_i$ 必须是第 $i$ 条边的颜色 ($1 \le C_i \le M$)。

接下来输出 $M$ 行。第 $i$ 行描述边 $i$ 的特殊旁路的颜色集合。该行必须以整数 $k_i$ ($1 \le k_i \le 8$) 开头，表示列表中的颜色数量。随后是 $k_i$ 个介于 $1$ 和 $M$ 之间的互不相同的整数：颜色列表。颜色可以以任意顺序输出。必须存在一条连接 $u_i$ 和 $v_i$ 的特殊旁路，且该路径不使用列表中颜色以外的任何颜色。注意，这意味着颜色列表不必是最小可能的，甚至可以存在仅使用列表一部分颜色的路径：检查程序仅确保所列出的颜色足以构成一条旁路。

样例

样例输入 1

10 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
1 4

样例输出 1

1 2 3 4 5 6 7 8 9 10 5
3 2 3 5
3 1 3 5
3 1 2 5
6 5 6 7 8 9 10
7 4 5 6 7 8 9 10
6 4 5 7 8 9 10
6 4 5 6 8 9 10
6 4 5 6 7 9 10
6 4 5 6 7 8 10
8 4 5 6 7 8 9 1 2
3 1 2 3

说明

在样例中，第一条边有两条旁路。 较长的那条包含 9 种颜色（从 2 到 10），因此它不是特殊的。 较短的那条由边 2、3 和 11（颜色 2、3 和 5）组成，因此它是特殊的。