E:排列城市
配点 : \(200\) 点
問題文
\(N\) 顶点 \(M\) 边被提供。 顶点编号从 \(1\) 到 \(N\),且给定图没有多边或自环。
输出一个长度为 \(N\) 的排列,满足以下条件。
- 对于每个 \(1 \leq i \leq N\),两个顶点 \(i, p_i\) 的距离 \(D(i, p_i) \) 要么是 1,要么是 2。
条件的排列都存在。 如果有多个选项,你可以输出其中任何一个。
\(D(u, v)\)距离顶点 \(u, v\) 定义为图中从顶点 \(u\) 到顶点 \(v\) 路径中包含的最小边数。
制約
- \(2 \leq N \leq 200000\)
- \(N-1 \leq M \leq 200000\)
- \(1 \leq u_i, v_i \leq N\) (\(1 \leq i \leq M)\)
- 表示在给定图中,顶点 \(u_i\) 和 \(v_i\) 之间存在无向边连接。 由
- 输入组成的图是连通的,不包含多边或自环。
- 所有输入值都是整数。 如果您想走
入力
输入是按以下格式从标准输入给出的。
\(N\) \(M\) \(u_1\) \(v_1\) \(u_2\) \(v_2\) \(\vdots\) \(u_M\) \(v_M\)
出力
的置换 \(p\),作为一个空间分离的顺序。
入力例 1
2 1 1 2
出力例 1
2 1
两个顶点之间的距离为 \(D(1, 2) = D(2, 1) = 1\),因此满足该条件。
入力例 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
2 3 4 1
如果你能想到多个答案,输出任何一个都正确。