output_description: 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.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 B_1
      :
      A_{N-1+M} B_{N-1+M}
attempt: #!/usr/bin/env python3
  N, M = map(int, input().split())
  g = [[] for _ in range(N)]
  rg = [[] for _ in range(N)]
  for _ in range(N - 1 + M):
      A, B = (int(x) - 1 for x in input().split())
      g[A].append(B)
      rg[B].append(A)
  
  
  def dfs(s):
      global ts
      global used
      used[s] = True
      for t in g[s]:
          if not used[t]:
              dfs(t)
      ts.append(s)
  
  
  def tsort():
      global ts
      for i in range(N):
          dfs(i)
      ts = ts[::-1]
  
  
  used = [False] * N
  ts = []
  tsort()
  
  mp = [None] * N
  for i, x in enumerate(ts):
      mp[x] = i
  
  ans = [0] * N
  for t in ts[1:]:
      if rg[t]:
          ans[t] = ts[max(mp[s] for s in rg[t])] + 1
  
  for x in ans:
      print(x)
  
problem_description: Statement
  
  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.
samples: [{"input": "3 1\n    1 2\n    1 3\n    2 3", "output": "0\n    1\n    2\n    \n\nThe graph in this input is shown below:\n\n![](https://img.atcoder.jp/nikkei2019-qual/ee05880ceecf703f656dd50bf22c573f.png)\n\nIt can be seen that this graph is obtained by adding the edge 1 \\rightarrow 3\nto the rooted tree 1 \\rightarrow 2 \\rightarrow 3.\n\n* * *"}, {"input": "6 3\n    2 1\n    2 3\n    4 1\n    4 2\n    6 1\n    2 6\n    4 6\n    6 5", "output": "6\n    4\n    2\n    0\n    6\n    2"}]