题目描述

$N$ 頂点の根付き木 (注記を参照) があり、その頂点には $1$ から $N$ までの番号が振られています。 根以外の各頂点には、その親から一本の有向辺が伸びています。 なお、根は頂点 $1$ とは限りません。

高橋くんは、このグラフに $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$ に向かって伸びていることを表します。

元の根付き木を復元してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$N$ 行出力せよ。 $i$ 行目には、頂点 $i$ が元の木の根であれば 0 を出力し、そうでなければ元の木で頂点 $i$ の親を表す整数を出力すること。

なお、元の木は一意に定まることが示せる。

题目大意

$n$ 个节点组成了一棵有根树，后面又增加了 $m$ 条有向边。

于是就成了 $n+m-1$ 条边的有向图，输入给定这个图。

这 $m$ 条边都是从原树的一个节点连上了自己的后代。

请求出原树的结构（对于节点 $1 \sim n$ 输出每个节点的父亲，如果是根节点则输出 $0$）。

Translated by WSXZCLXS

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

提示

注記

「木」や関連するグラフ理論の用語に関しては、Wikipediaの記事などをご覧ください。

制約

• $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)$
• 入力されるグラフは、$N$ 頂点の根付き木に問題文中の条件を満たす $M$ 本の辺を書き足すことで得られる。

Sample Explanation 1

入力されたグラフは次のようなものです。  これは、$1\ \rightarrow\ 2\ \rightarrow\ 3$ という根付き木に辺 $1\ \rightarrow\ 3$ を書き足したものであると考えられます。