题目描述

有 (N) 个小岛。国王收到了 (M) 条意见，每条意见要求在岛 (u_i) 与 (v_i) 之间建造一座无向桥。国王决定恰好建造这 (M) 座桥。

接下来要为每座桥分配建造公司。希望满足：

• 对于每个公司，即使该公司负责的所有桥全部不能通行，剩余桥仍能使所有岛互相连通；
• 在满足上述条件的前提下，实际委托的公司数量最少。

请输出一种满足条件的公司分配方案；若不存在，输出 -1。

输入格式

输入包含不超过 (40) 个数据集。

每个数据集格式如下：

N M
u1 v1
...
uM vM

(2\le N\le 150)，(N-1\le M\le 1500)。

不存在自环和重边。输入图保证连通。

输入以 0 0 结束。

输出格式

对每个数据集：

• 若无解，输出一行 -1；
• 否则输出两行：
  • 第一行输出公司数量 (K)；
  • 第二行输出 (M) 个整数，第 (i) 个整数表示第 (i) 座桥由哪家公司负责，编号需在 (1) 到 (K) 之间。

若存在多个解，输出任意一个。

样例输入

3 3
1 2
2 3
1 3
3 2
1 2
1 3
4 5
1 2
2 3
3 4
4 1
1 3
0 0

样例输出

3
2 3 1
-1
3
2 3 2 1 1