Problem:
 Score : 500 points    Problem 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.      Notes For "tree" and other related terms in graph theory, see the article in Wikipedia , for example.      Constraints  3 \leq N  1 \leq M  N + M \leq 10^5  1 \leq A_i, B_i \leq N  A_i \neq B_i  If i \neq j , (A_i, B_i) \neq (A_j, B_j) .  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.         Input Input is given from Standard Input in the following format:  N  M  A_1  B_1  :  A_{N-1+M}  B_{N-1+M}       Output 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.        Sample Input 1 3 1
1 2
1 3
2 3      Sample Output 1 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 .       Sample Input 2 6 3
2 1
2 3
4 1
4 2
6 1
2 6
4 6
6 5      Sample Output 2 6
4
2
0
6
2

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(N-1+M):
    A, B = map(int,input().split())
    A -= 1; B -= 1
    to[A].append(B)
    fr[B].append(A)






num = [0] * N


num = [len(fr[v]) for v in range(N)]

S = deque()
L = []

'''  編集　'''

for v in range(N):
    if num[v] == 0:
        S.append(v)
        
        '''　編集　'''

while S:
    v = S.popleft()
    L.append(v)
    for nv in to[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        
        ''' 　編集 '''


if len(L) != N:
    '''  編集　'''
    pass

index = [-1] * N
for i, v in enumerate(L):
    index[v] = i

for v in range(N):
    if v == L[0]:
        print(0)
        continue
    pv = -1
    d = N
    for cand in fr[v]:
        res = index[v] - index[cand]
        if res < d:
            d = res
            pv = cand
    pv += 1
    print(pv)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
parents = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    parents[B].add(A)

parent = [-1]*N
pool = list(range(N))
L = []
visited = [False]*N
while pool:
    i = pool.pop()
    if i >= N:
        L.append(i-N)
    elif visited[i]:
        continue
    else:
        visited[i] = True
        pool.append(i+N)
        for c in children[i]:
            pool.append(c)
L = L[::-1]
position = [None]*N
for i in range(N):
    position[L[i]] = i
for i in range(N):
    if not parents[i]:
        print(0)
    else:
        print(L[max(position[c] for c in parents[i])]+1)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(n-1+m)]

graph = [[] for _ in range(n)]
indegree = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]

for i in range(n-1+m):
    graph[edge[i][0]-1].append(edge[i][1]-1)
    indegree[edge[i][1]-1] += 1

root = indegree.index(0)
parent[root] = 0

queue = deque()
queue.append(root)

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        indegree[adj] -= 1
        if indegree[adj] == 0:
            queue.append(adj)
            parent[adj] = node+1

for p in parent:
    print(p)

Solution (Python):
import sys
from collections import deque
read = sys.stdin.read

N, M, *AB = map(int, read().split())
graph = [[] for _ in range(N + 1)]


parents = [0] * (N + 1)
for A, B in zip(*[iter(AB)] * 2):
    graph[A].append(B)
    parents[B] += 1

answer = [0] * (N + 1)
n = parents[1:].index(0) + 1
queue = deque([n])

while queue:
    V = queue.popleft()

    for v in graph[V]:
        
        parents[v] -= 1

        if parents[v] == 0:
            
            
            
            queue.append(v)
            answer[v] = V

print(*answer[1:], sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N,M=map(int,input().split())
par=[[] for _ in range(N)]
for _ in range(N-1+M):
  a,b=map(int,input().split())
  par[b-1].append(a)

dep=[-1]*N
def depth(n):
  if dep[n-1]!=-1:
    return dep[n-1]
  else:
    if len(par[n-1])==0:
      dep[n-1]=0
      return 0
    else:
      dep[n-1]=max([depth(i) for i in par[n-1]])+1
      return dep[n-1]

for i in range(N):
  if len(par[i])==0:
    print(0)
  elif len(par[i])==1:
    print(par[i][0])
  else:
    m=-1
    a=par[i][0]
    for j in par[i]:
      d=depth(j)
      if m<d:
        m=d
        a=j
    print(a)

Solution (Python):
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=deque([r])
while len(q)>0:
    u=q.popleft()
    for v in g[u]:
        ro[v-1]-=1
        if ro[v-1]==0:
            ans[v-1]=u+1
            q.append(v-1)
for i in ans:
    print(i)

Solution (Python):





from collections import deque

n, m = map(int, input().split())
g = tuple(set() for _ in range(n))  
ins = [0] * n  

for _ in range(n - 1 + m):
    s, t = (int(x) - 1 for x in input().split())
    
    g[s].add(t)  
    ins[t] += 1  

root = -1  
dq = deque((v, root) for v in range(n) if ins[v] == 0)  
res = [-1] * n  

while dq:
    v, root = dq.popleft()
    res[v] = root
    for u in g[v]:
        ins[u] -= 1  
        if ins[u] == 0:
            dq.append((u, v))  

res = (x + 1 for x in res)
print(*res, sep='\n')

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    to = defaultdict(set)
    ot = defaultdict(set)
    n, m = map(int, input().split())
    cnt_in_degree = [0] * n
    parent = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        cnt_in_degree[b] += 1
        to[a].add(b)
        ot[b].add(a)
    root = cnt_in_degree.index(0)
    parent[root] = -1
    part_roots = [root]
    cnt_decide = 1
    while cnt_decide < n:
        u = part_roots.pop()
        for ku in to[u]:
            if len(ot[ku]) == 1:
                parent[ku] = u
                part_roots.append(ku)
                cnt_decide += 1
            else:
                ot[ku].remove(u)
    for u in parent:
        print(u + 1)

main()

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
ie = dd(list)
inc = [0] * (N + 1)
for _ in range(N + M - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  ie[v].append(u)
  inc[v] += 1

def topologically(n, e, inc):
  res = []
  s = []
  c = 0
  many = 0
  for i in range(1, n + 1):
    if inc[i] == 0:
      s.append(i)
      c += 1
  many = c > 1
  while len(s):
    p = s.pop()
    res.append(p)
    for q in e[p]:
      inc[q] -= 1
      if inc[q] == 0:
        s.append(q)
    many = many or ((len(s) - c) > 0)
    c = len(s)
  return res
r = topologically(N, e, inc)
rrank = [0] * (N + 1)

for i in range(N):
  rrank[r[i]] = i

res = [0] * (N + 1)
for u in range(1, N + 1):
  t = -1
  for v in ie[u]:
    if rrank[v] > t:
      res[u] = v
      t = rrank[v]
for i in range(1, N + 1):
  print(res[i])

Solution (Python):
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
deg = [0]*N
parent = [[] for _ in range(N)]
for _ in range(N-1+M):
    x, y = map(int, input().split())
    edge[x-1].append(y-1)
    deg[y-1] += 1
    parent[y-1].append(x-1)
    
from collections import deque
res = list(v for v in range(N) if deg[v] == 0)
q = deque(res)
while q:
    v = q.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t] == 0:
            q.append(t)
            res.append(t)
    
res.reverse()
f = [0]*N
for i in range(N):
    f[res[i]] = i
    
ans = [0]*N
for i in range(N):
    if parent[i]:
        temp = parent[i][0]
        for p in parent[i]:
            if f[temp] > f[p]:
                temp = p
        ans[i] = temp+1
        
for i in range(N):
    print(ans[i])

Solution (Python):
import sys
input = sys.stdin.readline


N, M = map(int, input().split())

graph = [[] for _ in range(N)]
num_of_parent = [0]*N
for _ in range(N+M-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    num_of_parent[b-1] += 1

for i in range(N):
    if num_of_parent[i] == 0:
        root = i
        break

Parent = [None]*N
Parent[root] = 0
q = [root]
while q:
    qq = []
    for p in q:
        for np in graph[p]:
            num_of_parent[np] -= 1
            if num_of_parent[np] == 0:
                Parent[np] = p+1
                qq.append(np)
    q = qq

for p in Parent:
    print(p)

Solution (Python):
N, M = map(int, input().split())
G = [[] for _ in range(N)]
G1= [[] for _ in range(N)]
H = [0]*N
for _ in range(N+M-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G1[b-1].append(a-1)
    H[b-1]+=1
def topological_sort(G, H):
    res = []
    st0 = set()
    for v, n in enumerate(H):
        if n == 0:
            st0.add(v)
    while st0:
        v = st0.pop()
        res.append(v)
        for nv in G[v]:
            H[nv]-=1
            if H[nv] == 0:
                st0.add(nv)
    return res
res = topological_sort(G, H)
index = [-1]*N
for i, v in enumerate(res):
    index[v] = i
ans = [-1]*N
for v in res[1:]:
    nv = max(G1[v], key = lambda x:index[x])
    ans[v] = nv+1
ans[res[0]] = 0
print(*ans, sep = '\n')

Solution (Python):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
A,B=zip(*AB)
r=(set(range(1,N+1))-set(B)).pop()
def tsort():
    c=[[] for i in range(N)]
    t=[0]*N
    for i,j in AB:
        c[i-1].append(j-1)
        t[j-1]+=1
    s=[r-1]
    l=[]
    while len(s)>0:
        n=s.pop()
        l.append(n)
        for i in c[n]:
            t[i]-=1
            if t[i]==0:
                s.append(i)
    return l
cr=[[] for i in range(N)]
for i,j in AB:
    cr[j-1].append(i-1)
S=tsort()
o=[0]*N
for i,s in enumerate(S):
    o[s]=i
for i in range(N):
    x=-1
    for e in cr[i]:
        x=max(x,o[e])
    print(0 if x==-1 else S[x]+1)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,M = II()
A,B = Line(N-1+M,2)

parent = [[] for _ in range(N)]
parent_num = [0]*N
pt = [[] for _ in range(N)]

for i in range(N-1+M):
    parent[B[i]-1].append(A[i]-1)
    parent_num[B[i]-1] += 1
    pt[A[i]-1].append(B[i]-1)

for i in range(N):
    if parent[i]==[]:
        root = i

ans = ['0']*N
q = [root]
while q:
    q_new = []
    for q1 in q:
        for v in pt[q1]:
            if parent_num[v]==1:
                ans[v] = q1+1
                q_new.append(v)
            parent_num[v] -= 1
    q = q_new

for i in range(N):
    print(ans[i])

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()


N, M = list(map(int, input().split()))

graph = [[] for _ in range(N)]
depth = [0 for _ in range(N)]
parent_list = [[] for _ in range(N)]
parent_num = [0 for _ in range(N)]
parent = [-1 for _ in range(N)]

for i in range(N - 1 + M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)
	parent_list[B].append(A)
	parent_num[B] += 1

for i in range(N):
	if len(parent_list[i]) == 0:
		root = i
		break

que = deque([])
que.append(root)

while len(que) > 0:
	node = que.popleft()
	if len(graph[node]) > 0:
		for edge in graph[node]:
			depth[edge] = depth[node] + 1
			parent_num[edge] -= 1
			if parent_num[edge] == 0:
				que.append(edge)

for i in range(N):
	parent_depth = -1
	parent_node = -1
	if len(parent_list[i]) > 0:
		for p in parent_list[i]:
			if depth[p] > parent_depth:
				parent_depth = depth[p]
				parent_node = p
		parent[i] = parent_node



for i in range(N):
	print(parent[i] + 1)

Solution (Python):
from collections import deque

n,m = map(int,input().split())
g = [set() for _ in range(n+1)]
gg = [0]*(n+1)
for _ in range(n-1+m):
    a,b = map(int,input().split())
    g[a].add(b)
    gg[b] += 1
p = [-1]*(n+1)
q = deque()
for i in range(1,n+1):
  if gg[i] == 0:
    p[i] = 0
    q.append(i)
    break
while q:
  v = q.popleft()
  for x in g[v]:
    gg[x] -= 1
    if gg[x] == 0:
      q.append(x)
      p[x] = v
for x in p[1:]:
  print(x)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(node_num - 1 + edge_num)]

    parent_node = [0 for i in range(node_num + 1)]
    graph_data = defaultdict(set)
    nyuuji = [0 for i in range(node_num + 1)]

    for i in range(node_num - 1 + edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        nyuuji[b] += 1

    root = -1
    for i in range(1, node_num + 1):
        if nyuuji[i] == 0:
            root = i

    now_set = set()
    next_set = set()
    now_set.add(root)

    while len(now_set):
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                nyuuji[next_node] -= 1
                if nyuuji[next_node] == 0:
                    next_set.add(next_node)
                    parent_node[next_node] = now_node

        now_set = next_set
        next_set = set()

    for i in range(1, node_num + 1):
        print(parent_node[i])


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
ans = [-1] * N


@lru_cache(maxsize=None)
def search(now):
    if now == root:
        ans[now] = 0
        return 0
    ret = -1
    for pr in parent[now]:
        depth = search(pr)
        if depth > ret:
            ans[now] = pr + 1
            ret = depth
    return ret + 1

for i in range(N):
    search(i)

print(*ans, sep='\n')

Solution (Python):
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

L=[[]for i in range(N+1)]

I=[0 for i in range(N+1)]
for i in range(N+M-1):
    a,b=map(int,input().split())
    L[a].append(b)
    I[b]+=1
    


P=[-1 for i in range(N+1)]
S=-1
for i in range(1,N+1):
    if I[i]==0:
        P[i]=0
        S=i
        break

B=[]
cnt=0
for i in L[S]:
    if I[i]==1:
        B.append(i)
        P[i]=S
    else:
        I[i]-=1

for i in range(10**6):
    if cnt==len(B):
        break
    for j in L[B[cnt]]:
        if I[j]==1:
            B.append(j)
            P[j]=B[cnt]
        else:
            I[j]-=1
    cnt+=1
for i in range(1,N+1):
    print(P[i])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m = map(int, input().split())
G = [[] for i in range(n)]
rG = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    rG[b].append(a)
    used[b] = 1
root = used.index(0)

par = [-1]*n
depth = [-1]*n

def rec(cur):
    if depth[cur] != -1:
        return depth[cur]
    m = 0
    i = -1
    for p in rG[cur]:
        if rec(p)+1 > m:
            i = p
            m = rec(p)+1
    par[cur] = i
    depth[cur] = m
    return m

for i in range(n):
    rec(i)
par = [i+1 for i in par]
print(*par, sep="\n")

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    E = N+M-1
    edge = [set() for _ in range(N)]
    indegree = [0]*N
    for _ in range(E):
        a,b = MI_()
        edge[a].add(b)
        indegree[b]+=1
    
    queue = deque()
    for v in range(N):
        if not indegree[v]:
            queue.append(v)
    
    pop = queue.popleft
    ans = [0]*N
    topo_sort = []
    while queue:
        v = pop()
        topo_sort.append(v)

        for u in edge[v]:
            indegree[u]-=1
            if not indegree[u]:
                ans[u] = v + 1
                queue.append(u)
    print(*ans,sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):
def topological_sort(N, edges):
    from collections import deque
    nps=[0]*N
    for _, dsts in enumerate(edges):
        for dst in dsts:
            nps[dst]+=1
    
    q = deque([])
    for i, np in enumerate(nps):
        if np==0:
            q.append(i)
    
    rets = [0]*N
    cnt=0
    while q:
        src = q.popleft()
        rets[src]=cnt
        cnt+=1
        for dst in edges[src]:
            nps[dst]-=1
            if nps[dst]==0:
                q.append(dst)
    return rets

N,M=map(int,input().split())
edges=[[] for _ in range(N)]
revedges=[[] for _ in range(N)]

for _ in range(N-1+M):
    a,b=map(int,input().split())
    edges[a-1].append(b-1)
    revedges[b-1].append(a-1)

inds = topological_sort(N, edges)
parents=[-1]*N
for dst in range(N):
    if len(revedges[dst])==0:
        parents[dst]=0
    else:
        _,parents[dst] = max([(inds[src],src+1) for src in revedges[dst]])

for p in parents:
    print(p)

Solution (Python):
from collections import deque

N,M=map(int,input().split())
edges=[[] for _ in range(N)]
nps=[0]*N

for _ in range(N-1+M):
    a,b=map(int,input().split())
    edges[a-1].append(b-1)
    nps[b-1]+=1

arr=[[]]

for i,np in enumerate(nps):
    if np==0:
        arr[-1].append(i)

while arr[-1]:
    arr.append([])
    for src in arr[-2]:
        for dst in edges[src]:
            nps[dst]-=1
            if nps[dst]==0:
                arr[-1].append(dst)

gens=[0]*N
for gen, a in enumerate(arr):
    for n in a:
        gens[n]=gen

parents=[-1]*N
q=deque(arr[0])
while q:
    src = q.popleft()
    for dst in edges[src]:
        if gens[dst]-gens[src]==1:
            parents[dst]=src+1
            q.append(dst)

for p in parents:
    print(p if p>0 else 0)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,M = inpl()
lines = defaultdict(set)
incnts = [0]*N
for _ in range(N+M-1):
    x,y = inpl()
    x,y = x-1,y-1
    lines[x].add(y)
    incnts[y] += 1

s = incnts.index(0)
ans = [-1]*N
ans[s] = -1

q = queue.Queue()
q.put(s)
while not q.empty():
    s = q.get()
    for t in lines[s]:
        incnts[t] -= 1
        if incnts[t] == 0:
            ans[t] = s
            q.put(t)

for a in ans:
    print(a+1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N+M-1)]

out_edge = [set() for _ in range(N+1)]
in_edge = [set() for _ in range(N+1)]
for a,b in AB:
    out_edge[a].add(b)
    in_edge[b].add(a)


in_deg = [len(x) for x in in_edge]

q = [i for i,x in enumerate(in_deg[1:],1) if x == 0]

node_sorted = []
while q:
    x = q.pop()
    node_sorted.append(x)
    
    for y in out_edge[x]:
        in_deg[y] -= 1
        if in_deg[y] == 0:
            q.append(y)

node_rank = {x:i for i,x in enumerate(node_sorted,1)}
node_rank[0] = 0

answer = [0] * (N+1)
for a,b in AB:
    
    if node_rank[answer[b]] < node_rank[a]:
        answer[b] = a

print('\n'.join(map(str,answer[1:])))

Solution (Python):
import sys

from collections import deque
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [0] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B) 
    check_lst[B] += 1 

n = check_lst.index(0) 
ans = [0] * N 
que = deque()
q_append = que.append
q_append(n) 
q_left = que.popleft
while que:
    v = q_left()
    for v2 in lst[v]: 
        check_lst[v2] -= 1
        if check_lst[v2] == 0: 
            q_append(v2)
            ans[v2] = v + 1

print (*ans, sep = '\n')

Solution (Python):
import sys

from collections import deque
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [0] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] += 1

n = check_lst.index(0)
ans = [0] * N
que = deque()
que.append(n)
while que:
    v = que.popleft()
    for v2 in lst[v]:
        check_lst[v2] -= 1
        if check_lst[v2] == 0:
            que.append(v2)
            ans[v2] = v + 1
print (*ans, sep = '\n')

Solution (Python):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [set() for _ in [0]*N]
E2 = [set() for _ in [0]*N]
Eb = [set() for _ in [0]*N]
for a,b in AB:
    E[a-1].add(b-1)
    E2[a-1].add(b-1)
    Eb[b-1].add(a-1)

p = [0]*N
q = []
for i in range(N):
    if not E[i]:
        q.append(i)
while q:
    qq = set()
    for i in q:
        for j in Eb[i]:
            E[j].remove(i)
    for i in q:
        while Eb[i]:
            j = Eb[i].pop()
            if not E[j]:
                for k in E2[j]:
                    if p[k] == 0 : p[k] = j+1
                qq.add(j)
    q = qq

print(*p,sep="\n")

Solution (Python):
def tpsort(es):
    n = len(es)
    indgr = [0] * n
    for e in es:
        for u in e:
            indgr[u] += 1
    st = [v for v in range(n) if indgr[v] == 0]
    parent = [0] * n
    while st:
        v = st.pop()
        for u in es[v]:
            indgr[u] -= 1
            if indgr[u] == 0:
                st.append(u)
                parent[u] = v
    return parent

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N+M-1):
    a, b = map(int, input().split())
    es[a].append(b)
ans = tpsort(es)
for i in ans[1:]:
    print(i)

Solution (Python):
N,M=map(int,input().split())
from collections import defaultdict,deque
OUT=defaultdict(set)
cnt=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    OUT[a]|={b}
    cnt[b]+=1
check=deque([i for i in range(N) if cnt[i]==0])
ans=[N]*N
ans[check[0]]=0
while len(check)>0:
    now=check.popleft()
    for nex in OUT[now]:
        cnt[nex]-=1
        if cnt[nex]==0:
            ans[nex]=now+1
            check.append(nex)
for i in range(N):
    print(ans[i])

Solution (Python):
from collections import deque


N, M = map(int, input().split())
A, B = zip(*(map(int, input().split()) for _ in range(N - 1 + M)))


G = [set() for _ in range(N + 1)]
G_inv = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G[a].add(b)
    G_inv[b].add(a)
deg = [len(G_inv[i]) for i in range(N + 1)]
V = [i for i in range(1, N + 1) if not G_inv[i]]
deq = deque(V)
while deq:
    i = deq.popleft()
    for j in G[i]:
        deg[j] -= 1
        if deg[j] == 0:
            deq.append(j)
            V.append(j)

R = {i: r for r, i in enumerate(V)}
ans = '\n'.join(
    str(max(G_inv[i], key=lambda j: R[j], default=0))
    for i in range(1, N + 1)
)


print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
start={i for i in range(N) if IN[i]==0}
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
[print(p) for p in P]

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
Ans=[0]*(n+1)
Children=[[] for _ in range(n+1)]
Cnt=[0]*(n+1); Cnt[0]=1
for _ in range(n+m-1):
    a,b=map(int,input().split())
    Children[a].append(b)
    Cnt[b]+=1
root=Cnt.index(min(Cnt))
V=[root]
while V:
    v=V.pop()
    for u in Children[v]:
        if Cnt[u]==1:
            Ans[u]=v
            V.append(u)
        else:
            Cnt[u]-=1
print(*Ans[1:],sep='\n')

Solution (Python):
import collections

N, M = map(int, input().split())

ans = [0] * (N + 1)
parent = [0] * (N + 1)
parent[0] = N+M
child = [[] for i in range(N+1)]
deq = collections.deque()

for i in range(N+M-1):
    p, c = map(int, input().split())
    parent[c] += 1
    child[p].append(c)
root = parent.index(min(parent))
deq.append(root)
while len(deq) > 0:
    v = deq.pop()
    if len(child[v]) > 0:
        for u in child[v]:
            if parent[u] == 1:
                deq.appendleft(u)
                ans[u] = v
            else:
                parent[u] -= 1
for i in range(1,N+1):
    print(ans[i])

Solution (Python):
n,m = (int(i) for i in input().split())
x,y = [[] for i in range(n+1)],[0]*(n+1)
y[0] = 1
for i in range(n+m-1):
    a,b = (int(i) for i in input().split())
    x[a].append(b)
    y[b]+=1
ans,q = [0]*(n+1),[y.index(0)]
while q:
    p = q.pop()
    for i in x[p]:
        y[i]-=1
        if not y[i]:
            q.append(i)
            ans[i] = p
for i in ans[1:]: print(i)

Solution (Python):

from sys import stdin


import numpy as np


s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


from collections import deque
def topological_sort(graph, nodes):
    """

    Prameters
    ---------
    graph: list, [[parent, child], ...]
        graph[i][0]からgraph[i][1]へ
        コード上はv1が親ノード,v2が子ノード

    nodes : list
        全ノードのリスト

    Returns
    -------
    res : list
        トポロジカルソートされたノード
        インデックスが小さい方が親ノード側
    """
    outs = {i: [] for i in nodes}
    ins = {i: 0 for i in nodes}
    for v1, v2 in graph:
        outs[v1].append(v2)
        ins[v2] += 1

    queue = deque(i for i in nodes if ins[i] == 0)
    res = []
    while queue:
        v1 = queue.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                queue.append(v2)
    return res


N, M = ds_in()

parent = {i+1: [] for i in range(N)}
graph = []
for _ in range(N+M-1):
    a, b = ds_in()
    graph.append([a, b])
    parent[b].append(a)

res = topological_sort(graph, [i+1 for i in range(N)])

sorted_index = np.zeros(N+1, dtype=int)
sorted_index[res] = np.arange(N)

for i in range(1, N+1):
    if i == res[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])

Solution (Python):

from sys import stdin


import numpy as np


s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

candidates = []
for i, j in inflow.items():
    if j == 0:
        candidates.append(i)

sorted_edges = []
while len(sorted_edges) < N:
    par = candidates.pop()
    sorted_edges.append(par)
    for chi in child[par]:
        inflow[chi] -= 1
        if inflow[chi] == 0:
            candidates.append(chi)


sorted_index = np.zeros(N+1, dtype=int)
sorted_index[sorted_edges] = np.arange(N)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])

Solution (Python):
import sys
sys.setrecursionlimit(10**5+1)
n,m = map(int,input().split())
tree = [[] for i in range(n)]
tree_rev = [[] for i in range(n)]
for i in range(n-1+m):
    x, y = map(int, input().split())
    tree[x-1].append(y-1)
    tree_rev[y-1].append(x-1)

topological_sorted_n = []
visited = [False]*n

def topological_sort(i):
    if not visited[i]:
        visited[i] = True
        for next_i in tree[i]:
            topological_sort(next_i)
        topological_sorted_n.append(i)

for i in range(n):
    topological_sort(i)
topological_sorted_n = topological_sorted_n[::-1]

memo = {}
for i in range(n):
    memo[topological_sorted_n[i]] = i

for i in range(n):
    index = -1
    ans = 0
    for pos in tree_rev[i]:
        if index < memo[pos]:
            index = memo[pos]
            ans = pos+1
    print(ans)