← 返回题目列表

AtCoder · wupc2019_c

C. 排列城市

中文机器翻译题面 查看原题
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

如果你能想到多个答案,输出任何一个都正确。