配点 : $500$ 点

問題文

$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$ に向かって伸びていることを表します。

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

注記

「木」や関連するグラフ理論の用語に関しては、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$ 本の辺を書き足すことで得られる。

入力

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

$N$ $M$

$A_1$ $B_1$

$:$

$A_{N-1+M}$ $B_{N-1+M}$

出力

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

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

3 1
1 2
1 3
2 3

0
1
2

入力されたグラフは次のようなものです。

これは、$1 \rightarrow 2 \rightarrow 3$ という根付き木に辺 $1 \rightarrow 3$ を書き足したものであると考えられます。

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

6
4
2
0
6
2