{"raw_statement":[{"iden":"problem statement","content":"There is a rooted tree (see Notes) with $N$ vertices numbered $1$ to $N$. Each of the vertices, except the root, has a directed edge coming from its parent. Note that the root may not be Vertex $1$.\nTakahashi has added $M$ new directed edges to this graph. Each of these $M$ edges, $u \\rightarrow v$, extends from some vertex $u$ to its descendant $v$.\nYou are given the directed graph with $N$ vertices and $N-1+M$ edges after Takahashi added edges. More specifically, you are given $N-1+M$ pairs of integers, $(A_1, B_1), ..., (A_{N-1+M}, B_{N-1+M})$, which represent that the $i$\\-th edge extends from Vertex $A_i$ to Vertex $B_i$.\nRestore the original rooted tree."},{"iden":"notes","content":"For \"tree\" and other related terms in graph theory, see [the article in Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6)), for example."},{"iden":"constraints","content":"*   $3 \\leq N$\n*   $1 \\leq M$\n*   $N + M \\leq 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   $A_i \\neq B_i$\n*   If $i \\neq j$, $(A_i, B_i) \\neq (A_j, B_j)$.\n*   The graph in input can be obtained by adding $M$ edges satisfying the condition in the problem statement to a rooted tree with $N$ vertices."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$:$\n$A_{N-1+M}$ $B_{N-1+M}$"},{"iden":"sample input 1","content":"3 1\n1 2\n1 3\n2 3"},{"iden":"sample output 1","content":"0\n1\n2\n\nThe graph in this input is shown below:\n![image](https://img.atcoder.jp/nikkei2019-qual/ee05880ceecf703f656dd50bf22c573f.png)\nIt can be seen that this graph is obtained by adding the edge $1 \\rightarrow 3$ to the rooted tree $1 \\rightarrow 2 \\rightarrow 3$."},{"iden":"sample input 2","content":"6 3\n2 1\n2 3\n4 1\n4 2\n6 1\n2 6\n4 6\n6 5"},{"iden":"sample output 2","content":"6\n4\n2\n0\n6\n2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}