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
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,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
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
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()
    edge = [[]for _ in range(N)]
    indegree = [0]*N 
    for _ in range(M+N-1):
        a,b = MI_()
        edge[a].append(b)
        indegree[b] += 1
    
    
    queue = deque() 
    for i,x in enumerate(indegree):
        if not x:
            queue.append(i)
    
    pop = queue.popleft
    topological_index = [] 
    ans = [0]*N
    while queue:
        v = pop()
        topological_index.append(v)
    
        for to in edge[v]:
            indegree[to] -= 1
            if not indegree[to]:
                queue.append(to)
                ans[to]=v+1
    
    print(*ans,sep="\n")    
if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,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
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
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()
    edge = [[]for _ in range(N)]
    indegree = [0]*N 
    for _ in range(M+N-1):
        a,b = MI_()
        edge[a].append(b)
        indegree[b] += 1
    
    
    queue = deque() 
    for i,x in enumerate(indegree):
        if not x:
            queue.append(i)
    
    pop = queue.popleft
    topological_index = [] 
    ans = [0]*N
    while queue:
        v = pop()
        topological_index.append(v)
    
        for to in edge[v]:
            indegree[to] -= 1
            if not indegree[to]:
                queue.append(to)
                ans[to]=v+1
    
    print(*ans,sep="\n")    
if __name__ == '__main__':
    main()

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

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


add = np.zeros(N+1, dtype=int)
rank = [-1]*(N+1)


for i in range(1, N+1):
    add[i] = len(e_to[i])
    if len(e_to[i]) == 0:
        root = i


rank[root] = 0
node = deque([root])
while node:
    s = node.popleft()
    add[e_from[s]] -= 1
    for t in e_from[s]:
        if add[t] == 0:
            rank[t] = s
            node.append(t)

print(*rank[1:], sep="\n")

Solution (Python):
from collections import deque
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


add = np.zeros(N+1, dtype=int)
rank = [-1]*(N+1)


for i in range(1, N+1):
    add[i] = len(e_to[i])
    if len(e_to[i]) == 0:
        root = i


rank[root] = 0
node = deque([root])
while node:
    s = node.popleft()
    add[e_from[s]] -= 1
    for t in e_from[s]:
        if add[t] == 0:
            rank[t] = s
            node.append(t)

print(*rank[1:], sep="\n")

Solution (Python):
from collections import deque
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


add = np.zeros(N+1, dtype=int)
rank = [-1]*(N+1)


for i in range(1, N+1):
    add[i] = len(e_to[i])
    if len(e_to[i]) == 0:
        root = i


rank[root] = 0
node = deque([root])
while node:
    s = node.popleft()
    add[e_from[s]] -= 1
    for t in e_from[s]:
        if add[t] == 0:
            rank[t] = s
            node.append(t)

print(*rank[1:], sep="\n")

Solution (Python):
N,M=map(int,input().split())
es=[]
for _ in range(N-1+M):
    i,o=map(int,input().split())
    es.append((i-1,o-1))

from collections import defaultdict, deque
ins=defaultdict(int)
outs=defaultdict(list)

for i, o in es:
    outs[i].append(o)
    ins[o]+=1

q=deque()
for i in range(N):
    if ins[i]==0:
        q.append(i)
rank=[0]*N
while q:
    i=q.popleft()
    for o in outs[i]:
        ins[o]-=1
        if ins[o]==0:
            q.append(o)
            rank[o]=rank[i]+1
    
ans=[0]*N
for i in range(N):
    for x in outs[i]:
        if rank[x]-rank[i]==1:
            ans[x]=i+1

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
excess = [0 for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
  if len(tree_come[i]) >= 2:
    excess[i] = len(tree_come[i])-1
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
visited = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  if excess[x] >= 1:
    excess[x] -= 1
    continue
  for y in tree_go[x]:
    que.append((y,x))
print(*parent[1:],sep="\n")

Solution (Python):
from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(N-1+M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
rank = [0]*N
ans = [0]*N
while q:
    s = q.popleft()
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            rank[t] = rank[s]+1
            q.append(t)
for i in range(N):
    for x in G[i]:
        if rank[x] - rank[i] == 1:
            ans[x] = i+1
for x in ans:
    print(x)

Solution (Python):
from collections import deque
from collections import defaultdict
N, M = map(int, input().split())
d = [0]*N
G = defaultdict(list)
for i in range(N-1+M):
    s, t = map(int, input().split())
    d[t-1] += 1
    G[s-1].append(t-1)
q = deque([])
for i in range(N):
    if d[i] == 0:
        q.append(i)
rank = [0]*N
ans = [0]*N
while q:
    s = q.popleft()
    for t in G[s]:
        d[t] -= 1
        if d[t] == 0:
            rank[t] = rank[s]+1
            q.append(t)
for i in range(N):
    for x in G[i]:
        if rank[x] - rank[i] == 1:
            ans[x] = i+1
for x in ans:
    print(x)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
G = {i:[0,[]] for i in range(1,N+1)}
for _ in range(N+M-1):
    a,b = map(int,input().split())
    G[a][1].append(b)
    G[b][0] += 1
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if G[i][0]==0:
        cur = i
        break
que = deque([cur])
hist[cur] = 1
T = [-1 for _ in range(N+1)]
T[cur] = 0
while que:
    i = que.popleft()
    for j in G[i][1]:
        if hist[j]==0:
            G[j][0] -= 1
        if G[j][0]==0:
            que.append(j)
            T[j] = i
            hist[j] = 1
for i in range(1,N+1):
    print(T[i])

Solution (Python):
n, m = map(int, input().split())
inc = [0]*n
out = [[] for _ in range(n)]
parent = [[] for _ in range(n)]
for _ in range(n-1+m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  out[a].append(b)
  parent[b].append(a)
  inc[b] += 1

S = {i for i, c in enumerate(inc) if c == 0}
L = []
 
while S:
    k = S.pop()
    L.append(k)
    for m in out[k]:
        inc[m] -= 1
        if inc[m] == 0:
            S.add(m)

A = [(float("inf"), -1) for _ in range(n)]
D = {j:i for i, j in enumerate(L)}
A[L[0]] = (0, -1)
for i in range(1, n):
  now = L[i]
  d, t = A[now]
  for j in parent[now]:
    if d > i - D[j]:
      d = i - D[j]
      t = j
  A[now] = (d, t)
for i, j in A:
  print(j+1)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
side = [[]for _ in range(N)]
counts = [0]*N
ans = [0]*N

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

queue = deque([counts.index(0)])
while queue:
    q = queue.popleft()
    for i in side[q]:
        counts[i] -= 1
        if counts[i] == 0:
            ans[i] = q+1
            queue.append(i)

for i in ans:
    print(i)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


ans=0

n,m=LI()
g=[[] for i in range(n)]
p=[[] for i in range(n)]
for i in range(n+m-1):
    a,b=LI_()
    g[a].append(b)
    p[b].append(a)


def topological_sort(g):
    n=len(g)
    rt=[]
    indeg=[0]*n  
    for i in range(n):
        for j in g[i]:
            indeg[j]+=1
    
    
    q=deque()
    for i in range(n):
        if indeg[i]==0:
            q.append(i)
    
    while q:
        c=q.popleft()
        rt.append(c)
        for nb in g[c]:
            indeg[nb]-=1
            if indeg[nb]==0:
                q.append(nb)
    return rt

topos=topological_sort(g)
root=topos[0]

dc={}
for i,j in enumerate(topos):
    dc[j]=i

v=[-1]*n
def dfs(x):
    v[x]=1
    q=[x]
    while q:
        c=q.pop()
        for nb in g[c]:
            if v[nb]==-1:
                v[nb]=1
                q.append(nb)
                
                if p[nb]:
                    prs=sorted(p[nb],key=lambda x:-dc[x])
                    par[nb]=prs[0]+ 1
    return

par=[0]*n
par[root]=0

dfs(root)

for i in par:
    print(i)

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

N, M = map(int, input().split())
ins = [0]*N
outs = defaultdict(list)

for _ in range(N+M-1):
    Ai, Bi = map(int, input().split())
    ins[Bi-1] += 1
    outs[Ai-1].append(Bi-1)

ans = [-1]*N
q = deque([i for i in range(N) if ins[i]==0])

while q:
    v = q.popleft()
    
    for nv in outs[v]:
        ins[nv] -= 1
        
        if ins[nv]==0:
            ans[nv] = v
            q.append(nv)

for ans_i in ans:
    print(ans_i+1)

Solution (Python):
from collections import*

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		deg[t - 1] += 1
	q = deque()
	for i, d in enumerate(deg):
		if not d:
			q.append(i)
	ans = [0] * v
	while q:
		c = q.popleft()
		for n in g[c]:
			deg[n] -= 1
			if not deg[n]:
				q.append(n)
				ans[n] = c + 1
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()

Solution (Python):
def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		deg[t - 1] += 1
	q = []
	for i, d in enumerate(deg):
		if not d:
			q.append(i)
	ans = [0] * v
	while q:
		c = q.pop(0)
		for n in g[c]:
			deg[n] -= 1
			if not deg[n]:
				q.append(n)
				ans[n] = c + 1
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()

Solution (Python):
def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	rev = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		rev[t - 1].append(s - 1)
		deg[t - 1] += 1
	order = topologicalSort(g, deg)
	idx = [None] * v
	for i, o in enumerate(order):
		idx[o] = i
	ans = [0] * v
	for i in range(v):
		if rev[i]:
			ans[i] = max(rev[i], key=lambda x: idx[x]) + 1
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[トポロジカルソート]
⇒入次数0の頂点からスタートし、その番号を1とする.
　1から出ている有向辺をすべて削除
  入次数0になった頂点の番号を2とし、2から出ている有向辺をすべて削除
  入次数0になった頂点の番号を3とし、...を繰り返す

常に入次数が0になった頂点を選択してその1つ前を親とするため、
出来上がったグラフの各頂点の親は、そのグラフで最も近い親(距離1)
つまり、後から足されたM本の辺ではない
よって、トポロジカルソートによって得られるグラフが元の木である.
"""
n,m = LI()

edges = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(n-1+m):
    a,b = LI()
    edges[a-1].append(b-1)
    cnt[b-1] += 1


ans = [None]*n
que = deque()
for i in range(n):
    if cnt[i] == 0:
        que.append(i)
        ans[i] = 0
        while que:
            v = que.popleft()
            for i in edges[v]:
                cnt[i] -= 1
                if cnt[i] == 0:
                    que.append(i)
                    ans[i] = v+1
        break
for i in ans:
    print(i)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[トポロジカルソート]
⇒入次数0の頂点からスタートし、その番号を1とする.
　1から出ている有向辺をすべて削除
  入次数0になった頂点の番号を2とし、2から出ている有向辺をすべて削除
  入次数0になった頂点の番号を3とし、...を繰り返す

常に入次数が0になった頂点を選択してその1つ前を親とするため、
出来上がったグラフの各頂点の親は、そのグラフで最も近い親(距離1)
つまり、後から足されたM本の辺ではない
よって、トポロジカルソートによって得られるグラフが元の木である.
"""
n,m = LI()

edges = [[] for _ in range(n)]
cnt = [[0,i] for i in range(n)]
for _ in range(n-1+m):
    a,b = LI()
    edges[a-1].append(b-1)
    cnt[b-1][0] += 1


ans = [None]*n
que = deque()
for i in range(n):
    if cnt[i][0] == 0:
        que.append(cnt[i][1])
        ans[cnt[i][1]] = 0
        while que:
            v = que.popleft()
            for i in edges[v]:
                cnt[i][0] -= 1
                if cnt[i][0] == 0:
                    que.append(i)
                    ans[i] = v+1
        break
for i in ans:
    print(i)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()

edges = [[] for _ in range(n)]
cnt = [[0,i] for i in range(n)]
for _ in range(n-1+m):
    a,b = LI()
    edges[a-1].append(b-1)
    cnt[b-1][0] += 1


ans = [None]*n
que = deque()
for i in range(n):
    if cnt[i][0] == 0:
        que.append(cnt[i][1])
        ans[cnt[i][1]] = 0
        while que:
            v = que.popleft()
            for i in edges[v]:
                cnt[i][0] -= 1
                if cnt[i][0] == 0:
                    que.append(i)
                    ans[i] = v+1
        break
for i in ans:
    print(i)

Solution (Python):
from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    ab.append(tuple(map(int, input().split())))

in_cnt = defaultdict(int)
rev = defaultdict(list)
outs = defaultdict(list)
for a, b in ab:
    in_cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    rev[b - 1].append(a - 1)

res = []
queue = deque([i for i in range(N) if in_cnt[i] == 0])
while queue:
    v = queue.popleft()
    res.append(v)
    for v2 in outs[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i for i, v in sorted(enumerate(res), key=lambda x: x[1])]

ans = [0] * N
ans[res[0]] = 0
for v in res[:0:-1]:
    ans[v] = max([(order[v2], v2) for v2 in rev[v]])[1] + 1

for a in ans:
    print(a)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(n-1+m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        R[v].append(u)

    
    dp=[None]*n
    def dfs(v):
        if(dp[v] is not None):
            return dp[v]
        res=0
        for nv in E[v]:
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    for v in range(n):
        dfs(v)

    
    ans=[None]*n
    root=max((dp[v],v) for v in range(n))[1]
    ans[root]=-1
    for v in range(n):
        if(v==root): continue
        p=min((dp[p],p) for p in R[v])[1]
        ans[v]=p

    print(*map(lambda x:x+1,ans),sep='\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    R=[[] for _ in range(n)]
    for _ in range(n-1+m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        R[v].append(u)

    
    dp=[None]*n
    def dfs(v):
        if(dp[v] is not None):
            return dp[v]
        res=0
        for nv in E[v]:
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res
    for v in range(n):
        dfs(v)

    ans=[None]*n
    root=max((dp[v],v) for v in range(n))[1]
    ans[root]=-1

    
    for v in range(n):
        if(v==root): continue
        p=min((dp[p],p) for p in R[v])[1]
        ans[v]=p

    print(*map(lambda x:int(x+1),ans),sep='\n')
resolve()

Solution (Python):
def examD():
    N, M = LI()
    V = [[] for _ in range(N)]
    ans = [0]*N
    Cnt=[0]*(N+1); Cnt[N]=1
    for i in range(N+M-1):
        a, b = LI()
        V[a-1].append(b-1)
        Cnt[b-1] += 1
    root = Cnt.index(min(Cnt))
    que = [root]


    while que:
        v = que.pop()
        for u in V[v]:
            if Cnt[u] == 1:
                ans[u] = v+1
                que.append(u)
            else:
                Cnt[u] -= 1
    print(*ans, sep='\n')
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Solution (Python):
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1 + M)]

outs = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
parents = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    parents[b].append(a)
    outs[a] += 1

leaves = deque()
for v in range(1, N + 1):
    if not graph[v]:
        leaves.append(v)

order = [-1] * (N + 1)
j = 0

while leaves:
    v = leaves.popleft()
    for p in parents[v]:
        outs[p] -= 1
        if outs[p] == 0:
            leaves.append(p)
    order[v] = j
    j += 1

for v in range(1, N + 1):
    rejected_order = INF
    parent = 0
    for p in parents[v]:
        if rejected_order > order[p]:
            rejected_order = order[p]
            parent = p
    print(parent)

Solution (Python):
from collections import deque

N, M = map(int,input().split())
count = [0]*N
side = [[]for i in range(N)]
rside = [[]for i in range(N)]

for i in range(N+M-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    rside[b-1].append(a-1)
    count[b-1] += 1
root = count.index(0)
queue = deque([root])
top = [0]*N

for i in range(N):
    q = queue.popleft()
    top[q] = i
    for k in side[q]:
        count[k] -= 1
        if count[k] == 0:
            queue.append(k)
for i in range(N):
    if rside[i] == []:
        print(0)
        continue
    ret = root
    for j in rside[i]:
        if top[ret] < top[j]:
            ret = j
    print(ret+1)

Solution (Python):
from collections import deque

n,m = map(int,input().split())
outs = [[] for i in range(n)]
ins = [0]*n
ans = []
for i in range(n+m-1):
    a,b = map(int,input().split())
    outs[a-1].append(b-1)
    ins[b-1] += 1
S = deque([])
for i in range(n):
    if ins[i] == 0:
        S.append([i,i])
while len(S) > 0:
    cur = S.popleft()
    ans.append(cur)
    for e in outs[cur[0]]:
        ins[e] -= 1
        if ins[e] == 0:
            S.append([e,cur[0]])
ans.sort()
for i in range(n):
  if ans[i][0] == ans[i][1]:
    print(0)
  else:
    print(ans[i][1]+1)

Solution (Python):
from collections import deque

n,m = map(int,input().split())
outs = [[] for i in range(n)]
ins = [0]*n
ans = []
for i in range(n+m-1):
    a,b = map(int,input().split())
    outs[a-1].append(b-1)
    ins[b-1] += 1
S = deque([])
for i in range(n):
    if ins[i] == 0:
        S.append([i,i])
while len(S) > 0:
    cur = S.popleft()
    ans.append(cur)
    for e in outs[cur[0]]:
        ins[e] -= 1
        if ins[e] == 0:
            S.append([e,cur[0]])
ans.sort()
for i in range(n):
  if ans[i][0] == ans[i][1]:
    print(0)
  else:
    print(ans[i][1]+1)

Solution (Python):
from collections import deque

n,m = map(int,input().split())
DAG = [[] for i in range(n)]
ins = [0]*n
ans = []
for i in range(n+m-1):
    a,b = map(int,input().split())
    DAG[a-1].append(b-1)
    ins[b-1] += 1
S = deque([])
for i in range(n):
    if ins[i] == 0:
        S.append([i,i])
while len(S) > 0:
    cur = S.popleft()
    ans.append(cur)
    for e in DAG[cur[0]]:
        ins[e] -= 1
        if ins[e] == 0:
            S.append([e,cur[0]])
ans.sort()
for i in range(n):
  if ans[i][0] == ans[i][1]:
    print(0)
  else:
    print(ans[i][1]+1)

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

for l in AB:
    inc[l[1]-1] += 1
    out[l[0]-1].append(l[1]-1)

S = {i for i, c in enumerate(inc) if c == 0}

while S:
    n = S.pop()
    
    for m in out[n]:
        inc[m] -= 1
        if inc[m] == 0:
            S.add(m)
            ans[m] = n + 1 
print(*ans,sep="\n")

Solution (Python):
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*(n+m-1)]
    g2=[[] for _ in [0]*n]
    [g2[b-1].append(a-1) for a,b in ab]
    for i in range(n):
        if len(g2[i])==0:
            root=i
            break
    g2=[len(i) for i in g2]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    q=[root]
    r=[0]*n
    while q:
        qq=[]
        while q:
            i=q.pop()
            for j in g[i]:
                if g2[j]==1:
                    qq.append(j)
                    r[j]=i+1
                g2[j]-=1
        q=qq
    for i in r:
        print(i)
main()

Solution (Python):
N, M = map(int, input().split())
v = [[] for _ in range(N)]
u = [[] for _ in range(N)]
for _ in range(N + M - 1) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    u[B-1].append(A-1)

for i in range(N) :
    if len(u[i]) == 0 :
        s = i
        break
        
dist = [0] * N
par = [-1] * N
cnt = [0] * N

par[s] = -1
q = [s]
while q :
    cur = q.pop()
    cnt[cur] += 1
    if cur != s and cnt[cur] != len(u[cur]) :
        continue
        
    for nex in v[cur] :
        if dist[cur] + 1 > dist[nex] :
            dist[nex] = dist[cur] + 1
            par[nex] = cur
            q.append((nex))

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

Solution (Python):
from collections import defaultdict, deque


def getlist():
	return list(map(int, input().split()))

N, M = getlist()
outE = defaultdict(list)
inE = defaultdict(int)

for i in range(N + M - 1):
	u, v = getlist()
	outE[u - 1].append(v - 1)
	inE[v - 1] += 1

Q = deque()
for i in range(N):
	if inE[i] == 0:
		Q.append(i)
top = []
while Q:
	v1 = Q.popleft()
	top.append(v1)
	for v2 in outE[v1]:
		inE[v2] -= 1
		if inE[v2] == 0:
			Q.append(v2)

parent = [0] * N
for i in top:
	for j in outE[i]:
		parent[j] = i + 1
for i in range(N):
	print(parent[i])

Solution (Python):
from collections import deque

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

dic = {}
npflag = [True] * N
pnum = [0] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False
    pnum[B] += 1

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)
                

for i in range(N):

    print (p[i]+1)