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: from bisect import bisect_left
  from collections import deque
  
  N, M = map(int, input().split())
  AB = []
  for _ in range(N - 1 + M):
      a, b = map(int, input().split())
      AB.append((a, b))
  AB.sort(key=lambda x: x[0])
  BA = sorted(AB, key=lambda x: x[1])
  AB_A = [a for a, b in AB]
  BA_B = [b for a, b in BA]
  
  # find root
  root = 1
  while True:
      i = bisect_left(BA_B, root)
      if BA_B[i] != root:
          break
      root = BA[i][0]
  
  t_nl = [0] * (N + 1)
  # t_ln = [0] * (N + M + 1)
  t_ln = [0] * (100010)
  isdup_n = [True] * (N + 1)
  par_n = [0] * (N + 1)
  
  q = deque()
  q.append((root, 0))
  l = 1
  while len(q):
      n, p = q.popleft()
      t_nl[n] = l
      t_ln[l] = n
      if par_n[n] == 0:
          par_n[n] = p
      else:
          par_n[n] = par_n[n] if t_nl[par_n[n]] > t_nl[p] else p
          l += 1
          # continue
      i = bisect_left(AB_A, n)
      while i < len(AB_A) and AB_A[i] == n:
          q.append((AB[i][1], n))
          i += 1
      l += 1
  
  for v in par_n[1:]:
      print(v)
  
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"}]