配点 : 400 点
問題文
N 頂点 M 有一张边的无向单纯连通图。
这张图的顶点上有编号 1 到 N 以及边上有编号 1 到 M 。
辺 i (1 \le i \le M) 是顶点 u_i 和边 v_i 已经连接。
这个图具有以下特殊性质。
- 关于哪一条边 i (1 \le i \le M) 对顶点 u_i 和 v_i 的路径中,存在不使用边 i 的情况。
我们将这种路径称为“边” i 的应答路径。1 一条边的迂回路径可能存在复数条。
给图的每条边,从颜色 1 到颜色 M 中选择 M 种颜色中的 1 种进行涂色。在此情况下,必须满足以下条件。
- 连接到同一个顶点的 2 条边必须用不同的颜色涂。
- 对于任何一条边,该边的绕行路径上,至少存在 1 个满足以下条件的。
- 路径上包含的所有边所使用的颜色不超过 8 种。(※)
这种颜色涂法称为 1 请去寻找。
此外,对于这样涂色的图的每条边,上述 (※) 条件所满足的绕行路径 1 。 (输出方式比较特殊,具体请看输出结果。)
可以看出,这样的着色方法总是在以下约束下存在。
制約
- 3 \le N \le 5555
- 3 \le M \le \min(N(N-1)/2, 9999)
- 1 \le u_i < v_i \le N
- 1 \le i < j \le N ,(u_i, v_i) \neq (u_j, v_j)
- 给定的图形已连接。
- 关于哪一条边 i (1 \le i \le M) 对顶点 u_i 和 v_i 的路径中,存在不使用边 i 的情况。
部分点
- N \le 111 和 如果您对 M \le 222 的数据集,10 点。
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 390 点。
入力
输入将以以下形式从标准输入给出。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
如何应用符合条件的颜色 找到 1 并按以下格式输出。
1 边缘 要绘制的颜色 i (1 \le i \le M) 输出 C_i 以空格分隔。
i + 1 行目 (1 \le i \le M) 是满足以下条件的一组颜色 T_i 输出为 1 输出一。
- 1 \le |T_i| \le 8
- T_i 至 通过放置 不包括在内 颜色边缘和边缘 即使 i 从图中删除,顶点 u_i, v_i 是一个串联。
T_i 的大小 |T_i| 和T_i 至 通过放置 包括 打印全部 色 D_{i,j} (1 \le j \le |T_i|) 。
问题陈述中存在 T_i 和满足 (*) 的边 i 中存在绕行路径是等价的。
C_1 C_2 \ldots C_M
|T_1| D_{1,1} D_{1,2} \ldots D_{1,|T_1|}
|T_2| D_{2,1} D_{2,2} \ldots D_{2,|T_2|}
\vdots
|T_M| D_{M,1} D_{M,2} \ldots D_{M,|T_M|}
这里,输出必须满足以下条件。
- 1 \le C_i \le M (1 \le i \le M)
- 1 \le |T_i| \le 8 (1 \le i \le M)
- 1 \le D_{i,j} \le M (1 \le i \le M, 1 \le j \le |T_i|)
- D_{i,j} = D_{i,k} 纳鲁 j \ne k 不存在。 即使从图中删除了
- 辺 i 和T_i 中不包含的颜色的边,顶点 u_i, v_i 是一个串联。(1 \le i \le M)
- C_i 和 D_{i,j} 是一个整数。
满足这些条件的所有输出都是正确答案。
特别是 T_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
辺 1 的绕行路径,边缘 2 到边缘 有些使用的边缘达到 10 ,但这些边缘使用的颜色是 2 到颜色 10 中选择 9 类型,该路径不满足问题陈述的条件(*)。
然而,边缘 有些使用 1 的绕行路径,边缘 2, 3, 11 。这些边缘使用的颜色是 2, 3, 5 的 3 类型,因此该路径满足问题陈述的条件(*)。