AT_kupc2020_i Coloring Paths

有一个包含 $N$ 个顶点、$M$ 条边的无向简单连通图。 该图的顶点编号为 $1$ 到 $N$，边的编号为 $1$ 到 $M$。 第 $i$ 条边 $(1 \le i \le M)$ 连接顶点 $u_i$ 和顶点 $v_i$。 这个图具有如下特殊性质： - 对于任意一条边 $i\ (1 \le i \le M)$，都存在一条不经过边 $i$ 的、连接 $u_i$ 和 $v_i$ 的路径。 我们将这样的路径称为“边 $i$ 的迂回路径”。一条边的迂回路径可能有多条。 现在要用 $M$ 种颜色（颜色编号为 $1$ 到 $M$），为图中的每一条边选择一种颜色进行染色。此时，必须满足以下条件： - 连接同一顶点的两条边，必须染成不同的颜色。 - 对于任意一条边，都存在一条该边的迂回路径，且该路径上所经过的所有边所用的颜色种类不超过 $8$ 种。（※） 请你求出一种满足上述条件的染色方案。 此外，对于染色后的图中的每一条边，请你分别求出一条满足上面（※）条件的迂回路径所用到的颜色集合 $T_i$（输出方式较特殊，详见输出格式）。 在下述约束条件下，可以保证一定存在满足条件的染色方案。

输入以如下格式从标准输入读入。 > $N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

请输出一种满足条件的染色方案，格式如下： 第 $1$ 行输出 $M$ 个用空格分隔的整数，表示第 $i$ 条边染的颜色 $C_i$。 第 $i+1$ 行 $(1 \le i \le M)$ 输出一个颜色集合 $T_i$，满足： - $1 \le |T_i| \le 8$ - 将不属于 $T_i$ 的颜色的边和第 $i$ 条边从图中删除后，顶点 $u_i$ 和 $v_i$ 仍然连通。 输出 $T_i$ 时，先输出 $|T_i|$，然后输出 $T_i$ 中所有颜色 $D_{i,1}, D_{i,2}, \ldots, D_{i,|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|)$ - 不存在 $j \ne k$ 使得 $D_{i,j} = D_{i,k}$ - 将第 $i$ 条边和所有颜色不属于 $T_i$ 的边从图中删除后，$u_i$ 和 $v_i$ 仍然连通。$(1 \le i \le M)$ - $C_i$ 以及 $D_{i,j}$ 均为整数。 只要满足上述条件，输出均视为正确。 **特别地，$T_i$ 可以包含未在满足（※）的迂回路径中使用的颜色。**

### 约束条件 - $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) \ne (u_j, v_j)$ - 输入的图是连通的。 - 对于任意一条边 $i\ (1 \le i \le M)$，都存在一条不经过边 $i$ 的、连接 $u_i$ 和 $v_i$ 的路径。 ### 部分分 - 对于 $N \le 111$ 且 $M \le 222$ 的数据集，答对可得 $10$ 分。 - 对于无额外约束的数据集，答对可得 $390$ 分。 ### 样例解释 1 对于边 $1$ 的迂回路径，可以使用边 $2$ 到边 $10$，这些边所用的颜色为 $2$ 到 $10$，共 $9$ 种，不满足题目条件（※）。但也存在一条迂回路径仅使用边 $2$、$3$、$11$，这些边所用的颜色为 $2$、$3$、$5$，共 $3$ 种，满足题目条件（※）。 由 ChatGPT 4.1 翻译