AT_nikkei2019_qual_d Restore the Tree

[problemUrl]: https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d $ 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 $ の親を表す整数を出力すること。 なお、元の木は一意に定まることが示せる。

### 注記 「木」や関連するグラフ理論の用語に関しては、[Wikipediaの記事](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))などをご覧ください。 ### 制約 - $ 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 入力されたグラフは次のようなものです。 !\[\](https://img.atcoder.jp/nikkei2019-qual/ee05880ceecf703f656dd50bf22c573f.png) これは、$ 1\ \rightarrow\ 2\ \rightarrow\ 3 $ という根付き木に辺 $ 1\ \rightarrow\ 3 $ を書き足したものであると考えられます。