Score : 500 points
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.
Takahashi 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.
You 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.
Restore the original rooted tree.
For "tree" and other related terms in graph theory, see the article in Wikipedia, for example.
Input is given from Standard Input in the following format:
N M A_1 B_1 : A_{N-1+M} B_{N-1+M}
Print N lines.
In the i-th line, print 0
if Vertex i is the root of the original tree, and otherwise print the integer representing the parent of Vertex i in the original tree.
Note that it can be shown that the original tree is uniquely determined.
3 1 1 2 1 3 2 3
0 1 2
The graph in this input is shown below:
It can be seen that this graph is obtained by adding the edge 1 \rightarrow 3 to the rooted tree 1 \rightarrow 2 \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