时间限制：2 秒
空间限制：512 MiB

题目描述

给定一张无向简单连通图，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

这张图满足一个特殊性质：对于每条边 $i$，即使不使用这条边，也存在一条从 $u_i$ 到 $v_i$ 的路径。这样的路径称为第 $i$ 条边的 绕行路径。同一条边可能有多条绕行路径。

你需要给每条边染一种颜色。颜色编号为 $1$ 到 $M$。每条边恰好染一种颜色；有些颜色可以不用，有些颜色也可以被多条边使用。

一种边染色被称为有趣的，当且仅当满足以下条件：

1. 若两条边有公共端点，则它们的颜色不同；
2. 对于每条边，都存在一条特殊绕行路径：这条绕行路径上所有边的颜色种类数不超过 $8$。

你需要构造一种有趣染色，并且对于每条边，输出一个可用于构造其特殊绕行路径的颜色集合。

可以证明，在题目约束下至少存在一种有趣染色。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示第 $i$ 条边。

保证每一对顶点至多出现一条边，图连通，并且删除任意一条边后，该边两端点之间仍存在绕行路径。

输出格式

第一行输出 $M$ 个整数。第 $i$ 个整数 $C_i$ 表示第 $i$ 条边的颜色，要求

接下来输出 $M$ 行。第 $i$ 行描述第 $i$ 条边的特殊绕行路径可使用的颜色集合。

该行先输出一个整数 $k_i$，满足

然后输出 $k_i$ 个两两不同、范围在 $1$ 到 $M$ 之间的颜色编号。

对于第 $i$ 条边，必须存在一条从 $u_i$ 到 $v_i$ 的绕行路径，并且这条路径不使用集合之外的颜色。集合不要求最小；实际路径可以只用到集合中的一部分颜色。

数据范围

• $3\le N\le 5555$；
• $3\le M\le \min\left(\frac{N(N-1)}{2},9999\right)$；
• $1\le u_i<v_i\le N$；
• 图为简单连通图；
• 删除任意一条边后，其两个端点之间仍存在路径。

样例 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 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$，因此是特殊绕行路径。