分数: 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