← 返回题目列表

AtCoder · kupc2020_i

I. 着色路径

中文机器翻译题面 查看原题

配点 : 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 类型,因此该路径满足问题陈述的条件(*)。