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: def getN():
      return int(input())
  
  def getMN():
      a = input().split()
      b = [int(i) for i in a]
      return b[0],b[1]
  
  def getlist():
      a = input().split()
      b = [int(i) for i in a]
      return b
  
  
  from collections import deque
  
  n, m = getMN()
  
  parents = [[] for i in range(n+1)]
  childs = [[] for i in range(n+1)]
  
  k = m-1+n
  for i in range(k):
      p1,p2 = getMN()
      parents[p2].append(p1)
      childs[p1].append(p2)
  
  dst = [0 for i in range(n+1)]
  
  d = deque()
  n_root = 0
  for i, x in enumerate(parents[1:]):
      if not x:
          n_root = i+1
          break
  
  def bfs(n_cur):)
      for c in childs[n_cur]:
          d.append(c)
          dst[c] = max(dst[c], dst[n_cur]+1)
      while(d):
          bfs(d.pop())
  
  bfs(n_root)
  
  for plist in parents[1:]:
      if plist:
          cur = -1
          ans = plist[0]
          for p in plist:
              if dst[p] > cur:
                  cur = dst[p]
                  ans = p
          print(ans)
      else:
          print(0)
  
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"}]