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 翻译