← 返回题目列表

AtCoder · nikkei2019_qual_d

D. 恢复树

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

分数: 500 点

问题陈述

有一棵有根的树(见注释) N 顶点编号 1 to N。 除了根之外,每个顶点都有一条来自其父顶点的有向边。 注意根不能是Vertex 1.

高桥已添加 M 该图的新有向边。 这些中的每一个 M 边缘, u \rightarrow v,从某个顶点延伸 u 到其后代 v.

给你有向图 高桥添加边缘后的 N 顶点和 N-1+M 边缘。 更具体地说,您将获得 N-1+M 整数对, (A_1, B_1), ..., (A_{N-1+M}, B_{N-1+M}),这代表 i第一条边从顶点延伸 A_i 到顶点 B_i.

恢复原来的有根树。

注释

对于图论中的“树”和其他相关术语,请参见 维基百科中的文章 例如。

约束

  • 3 \leq N
  • 1 \leq M
  • N + M \leq 10^5
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • If i \neq j, (A_i, B_i) \neq (A_j, B_j).
  • 输入中的图形可以通过添加来获得 M 满足问题陈述中的条件的边到有根树 N 顶点。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
:
A_{N-1+M} B_{N-1+M}

输出

打印 N 行。 在 i第行,打印 0 如果顶点 i 是原始树的根,否则打印代表 Vertex 的父级的整数 原始树中的 i 。

请注意,可以证明原始树是唯一确定的。


示例输入 1

3 1
1 2
1 3
2 3

示例输出 1

0
1
2

此输入中的图表如下所示:

可以看出这个图是通过添加边得到的 1 \rightarrow 3 到有根树 1 \rightarrow 2 \rightarrow 3.


示例输入 2

6 3
2 1
2 3
4 1
4 2
6 1
2 6
4 6
6 5

示例输出 2

6
4
2
0
6
2