题目描述

有一棵有根树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。除根顶点外，每个顶点都有一条来自其父顶点的有向边。请注意，根可能不是顶点 $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})$ ，它们表示从顶点 $A_i$ 到顶点 $B_i$ 的 $i$ 条边。

你的任务是找到原来树的形态。

输入格式

第一行输入 $N,M$

接下来 $N+M-1$ 行每行两个整数代表一条边

输出格式

打印 $N$ 行。在 $i$ -th 行中，如果顶点 $i$ 是原始树的根，则打印 0，否则打印代表原始树中顶点 $i$ 父节点的整数。

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

3 1
1 2
1 3
2 3

0
1
2

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

6
4
2
0
6
2

样例 1 解释

该输入的图表如下所示：

可以看出，这个图是在有根树 $1 \rightarrow 2 \rightarrow 3$ 上添加边 $1 \rightarrow 3$ 得到的。

提示

• $3 \leq N$
• $1 \leq M$
• $N + M \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• 如果 $i \neq j$ , $(A_i, B_i) \neq (A_j, B_j)$ .
• 将满足问题陈述条件的 $M$ 条边添加到有 $N$ 个顶点的有根树中，即可得到输入的图形。