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):
from collections import deque

def resto(n,m,ab):

    oya=[[] for _ in range(n)]
    ko=[[] for _ in range(n)]

    for i,y in ab:
        oya[y-1]+=[i-1]
        ko[i-1]+=[y-1]

    root=0
    for i in range(n+m):
        if len(oya[i])==0:
            root=i
            break

    oya[root]=['a']
    deq=deque([root])
    while len(deq)>0:
        z=deq.popleft()
        for i in ko[z]:
            if len(oya[i])!=1:
                oya[i].remove(z)
            else:
                deq.append(i)

    ans=[str(0)+'\n' if i[0]=='a' else str(i[0]+1)+'\n' for i in oya ]

    return ''.join(ans)

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

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Pcan = defaultdict(lambda: 0)

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Pcan[B-1] += 1
par = list(Par)[0]
dist = [0]*N
Q = deque([par])

while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if Pcan[en] == 1:
                Q.append(en)
            else:
                Pcan[en] -= 1
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)

Solution (Python):



from collections import deque, defaultdict

V, E = map(int, input().split())
g = defaultdict(set)

h = defaultdict(int)


for _ in range(V - 1 + E):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    
    g[s].add(t)
    
    h[t] += 1

root = -1


q = deque((v1, root) for v1 in range(V) if h[v1] == 0)


res = [-1] * V


while q:
    
    v1, root = q.popleft()
    res[v1] = root
    for v2 in g[v1]:
        h[v2] -= 1
        
        if h[v2] == 0:
            q.append((v2, v1))
            

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

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

A = [[] for _ in range(N)]
P = [0]*N
C = [0]*N
root = -1

for (a,b) in AB:
    
    A[a-1].append(b-1)
    C[b-1] += 1

for i in range(N):
    if C[i]==0:
        root = i
P[root] = -1

from collections import deque
que = deque((a,root) for a in A[root])
while que:
    n,par = que.popleft()
    C[n] -= 1
    if C[n]==0:
        P[n] = par
        for i in A[n]:
            que.append((i,n))

for p in P:
    print(p+1)

Solution (Python):




import sys
sys.setrecursionlimit(1000000)
back = []


def calc(e):
    global back
    

    if back[e][1] == -1:
        if len(back[e][0]) == 0:
            back[e][1] = 0
            
            return 0
        elif len(back[e][0]) == 1:
            l = calc(back[e][0][0]) + 1
            back[e][1] = l
            
            return l
        maxl = calc(back[e][0][0])
        maxi = 0
        for i, s in enumerate(back[e][0][1:], 1):
            l = calc(s)
            if l >= maxl:
                maxl = l
                back[e][0][maxi] = -1
                maxi = i
            else:
                back[e][0][i] = -1
        back[e][1] = maxl + 1
        
        return maxl + 1
    else:
        
        return back[e][1]


def main():
    global back
    N, M = [int(i) for i in raw_input().strip().split(' ')]

    A = []
    for _ in range(N+M-1):
        A.append([int(i)-1 for i in raw_input().strip().split(' ')])
    

    back = [[[], -1] for _ in range(N)]

    for s, e in A:
        back[e][0].append(s)
    

    for i, b in enumerate(back):
        if b[1] == -1:
            
            calc(i)

    
    for b in back:
        if b[0] == []:
            print 0
        else:
            for s in b[0]:
                
                if s != -1:
                    print s+1


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())

result = [-1] * (N + 1)
edge_from = [[] for _ in range(N + 1)]
edge_to = [[] for _ in range(N + 1)]

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

parent = []
for i in range(1, N + 1):
    if any(edge_to[i]) and not any(edge_from[i]):
        parent.append(i)
        result[i] = 0
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if not any(edge_from[child]):
                result[child] = p
                next_.append(child)
    if not any(next_):
        break
    parent = next_

for x in result[1:]:
    print(x)

Solution (Python):


import sys
import math
import fractions
import heapq
import collections
import re
import array
import bisect
sys.setrecursionlimit(1000000)

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))


II = lambda: int(input())
MI = lambda: map(int, input().split())



def main():
    N, M = MI()
    in_edges = [set() for _ in range(N)]
    out_edges = [set() for _ in range(N)]
    num_in_edges = [0] * N
    for _ in range(N - 1 + M):
        a, b = MI()
        a -= 1
        b -= 1
        num_in_edges[b] += 1
        in_edges[b].add(a)
        out_edges[a].add(b)
    Root = argmin(num_in_edges)
    parent = [0] * N
    parent[Root] = -1

    q = [Root]

    while q:
        v = q.pop()
        for child in out_edges[v]:
            in_edges[child].remove(v)
            num_in_edges[child] -= 1
            if num_in_edges[child] == 0:
                parent[child] = v
                q.append(child)

    for p in parent:
        print(p + 1)


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

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

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_

for x in result:
    print(x + 1)

Solution (Python):
N, M = map(int, input().split())

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

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

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1
        break

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_.copy()

for x in result:
    print(x + 1)

Solution (Python):
N, M = map(int, input().split())

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

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

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if len(next_) == 0:
        break
    parent = next_.copy()

for x in result:
    print(x + 1)

Solution (Python):
from collections import deque, defaultdict

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

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

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [0] + [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
ans = [0] * (N + 1)
ans[sorted_ans[0] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
    
for a in ans[1:]:
    print(a)

Solution (Python):
from collections import deque, defaultdict

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

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

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
order = [0] + order
ans = [0] * (N + 1)
ans[sorted_ans[0] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
ans.pop(0)
for a in ans:
    print(a)

Solution (Python):
from collections import deque, defaultdict

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

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

queue = deque(i for i in range(1, N + 1) if in_cnt[i] == 0)
sorted_ans = []

while len(queue) != 0:
    v = queue.popleft()
    sorted_ans.append(v)
    for v2 in out[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i + 1 for i, v in sorted(enumerate(sorted_ans), key=lambda x: x[1])]
order = [0] + order
ans = [0] * (N + 1)
ans[sorted_ans[sorted_ans[0]] + 1] = 0

for v in sorted_ans[:0:-1]:
    ans[v] = max((order[v2], v2) for v2 in rev[v])[1]
ans.pop(0)
for a in ans:
    print(a)

Solution (Python):
from collections import deque

n,m = map(int,input().split())

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break


used = [0]*n
used[root]=1


def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    

def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            res[e]=z+1
            tank2.append(e)
            usedtank.append(e)


c = 1
tank = deque([root])
tank2 = deque([root])
usedtank = []

while c != n:
    tank = tank2
    tank2 = deque([])
    usedtank = []
    while len(tank)!=0:
        f(tank.popleft())
    for e_used in usedtank:
        used[e_used]=1
    c += len(tank2)
    
for i in range(n):
    print(res[i])

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1+M)]
indeg_n = [0]*N
indeg = [[] for i in range(N)]
outdeg = [[] for i in range(N)]
for a,b in src:
    indeg_n[b] += 1
    indeg[b].append(a)
    outdeg[a].append(b)

root = indeg_n.index(0)
toposo = []
stack = [root]

while stack:
    v = stack.pop()
    toposo.append(v)
    for to in outdeg[v]:
        indeg_n[to] -= 1
        if indeg_n[to] == 0:
            stack.append(to)

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

ans = [-1]*N
ans[root] = 0
for ti in range(1,N):
    v = toposo[ti]
    maxo = max(order[p] for p in indeg[v])
    ans[v] = toposo[maxo] + 1
print(*ans, sep='\n')

Solution (Python):
from collections import deque

n,m = map(int,input().split())

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break


used = [0]*n
used[root]=1


def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    

def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            res[e]=z+1
            tank2.append(e)
            usedtank.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
usedtank = []
while c != n:
    tank = tank2
    tank2 = deque([])
    usedtank = []
    while len(tank)!=0:
        f(tank.popleft())
    for usede in usedtank:
        used[usede]=1
    c += len(tank2)
    
for i in range(n):
    print(res[i])

Solution (Python):
from collections import defaultdict,deque
N,M = map(int,input().split())
es = [[int(x) for x in input().split()] for _ in range(N+M-1)]
ins = defaultdict(int)
outs = defaultdict(list)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
q = deque(v1 for v1 in range(N) if ins[v1]==0)
res = []
ans,c = [0 for i in range(N+1)],0
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2]==0:
            q.append(v2)
            ans[v2]=v1

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

Solution (Python):
def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    
    parent = [0]*V
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    while Q:
        del_node = Q.pop()
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)
                parent[j] = del_node+1

    return parent


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

    ans = topological_sort(N, E_in, E_from)
    for s in ans:
        print(s)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n+m-1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

P = [0] * (n+1)
D = [0] * (n+1)

def dfs(i):
    if D[i] > 0:
        return D[i] + 1
    for t in RT[i]:
        d = dfs(t)
        if d > D[i]:
            D[i] = d
            P[i] = t

    return D[i] + 1

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

D[root(1)] = 1

for i in range(1, n+1):
    dfs(i)

for p in P[1:]:
    print(p)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n+m-1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

P = [0] * (n+1)
D = [0] * (n+1)

def dfs(i):
    if D[i] > 0:
        return D[i] + 1
    for t in RT[i]:
        d = dfs(t)
        if d > D[i]:
            D[i] = d
            P[i] = t

    return D[i] + 1

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

D[root(1)] = 1

for i, t in enumerate(T):
    if not t:
        dfs(i)

for p in P[1:]:
    print(p)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
count = [0] * (N + 1)
ans = [0] * (N + 1)
for a, b in AB:
    G[a].add(b)
    count[b] += 1
for i in range(1, N):
    if count[i] == 0:
        root = collections.deque([i])
        break
while root:
    p = root.popleft()
    for c in G[p]:
        count[c] -= 1
        if count[c] == 0:
            ans[c] = p
            root.append(c)
print(*ans[1:], sep='\n')

Solution (Python):
from collections import*
v,n=map(int,input().split())
n+=v-1
es=[[int(x)for x in input().split()]for _ in range(n)]
outs=defaultdict(list)
ins=defaultdict(int)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2]+=1
q=deque(v1 for v1 in range(v)if not ins[v1])
res=[]
p=[0]*-~v
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
            p[v2]=v1
for t in p[1:]:print(t)

Solution (Python):
import sys

sys.setrecursionlimit(2000000)

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

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

for i in range(N-1+M):
  A,B=map(int,input().split())
  child[A-1].append(B-1)
  parent[B-1].append(A-1)
  
for i in range(N):
  if len(parent[i])==0:
    root=i
    break


kazu=[0]*N
for i in range(N):
  kazu[i]=len(parent[i])

answer=[0]*N

def dfs(index):
  search=[]
  for d in child[index]:
    kazu[d]-=1
    if kazu[d]==0:
      search.append(d)
      answer[d]=index+1
  for s in search:
    dfs(s)
    
 
dfs(root)

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):

    in_n = [0] * (N+1)
    g = defaultdict(list)
    rg = defaultdict(list)
    for a, b in AB:
        in_n[b] += 1
        g[a].append(b)
        rg[b].append(a)

    r = []
    for i, n in enumerate(in_n):
        if i != 0 and n == 0:
            r.append(i)

    sv = []
    while r:
        u = r.pop()
        sv.append(u)
        for v in g[u]:
            in_n[v] -= 1
            if in_n[v] == 0:
                r.append(v)

    svd = {}
    for i, v in enumerate(sv):
        svd[v] = i
    for i in range(1, N+1):
        mi = 0
        if len(rg[i]) == 0:
            print(0)
        else:
            for j in rg[i]:
                mi = max(mi, svd[j])
            print(sv[mi])
    return


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N+M-1)]
    slv(N, M, AB)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(500000)

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]

for _ in range(N + M - 1):
    u, v = [int(elem) - 1 for elem in fin().split()]
    adj[u].append(v)

inv_adj = [[] for _ in range(N)]
for u, neighbors in enumerate(adj):
    for v in neighbors:
        inv_adj[v].append(u)

topo = []
visited = [False] * N

def dfs_visit(node):
    for neighbor in adj[node]:
        if visited[neighbor]:
            continue
        visited[neighbor] = True
        dfs_visit(neighbor)
    topo.append(node)
    return

for node in range(N):
    if not visited[node]:
        visited[node] = True
        dfs_visit(node)

topo = topo[::-1]

parent = [-1] * N
order = dict()
order[topo[0]] = 0
for number, node in enumerate(topo[1:], start=1):
    neighbors = inv_adj[node]
    correct_parent = -1
    for neighbor in neighbors:
        if neighbor in order and order[neighbor] > correct_parent:
            correct_parent = order[neighbor]
    parent[node] = correct_parent
    order[node] = number

order_to_number = {v: k + 1 for k, v in order.items()}
order_to_number[-1] = 0

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

Solution (Python):
from collections import deque

n, m = map(int, input().split())

n_in = [0] * n
graph = [[] for _ in range(n)]
for i in range(n+m-1):
    A, B = map(int, input().split())
    n_in[B-1] += 1
    graph[A-1].append(B-1)

root = 0
for i in range(n):
    if n_in[i] == 0:
        root = i
        break

parent = [0] * n
q = deque([root])
count = 0
while q:
    node = q.popleft()
    for next_v in graph[node]:
        parent[next_v] = node+1
        n_in[next_v] -= 1
        if n_in[next_v] == 0:
            q.append(next_v)

for i in range(n):
    print(parent[i])

Solution (Python):
def topological_sort(V,E_from,E_in):
    IN = [-1]*V
    n = [-1]*V
    for v in range(V):
        IN[v] = len(E_in[v])
        if IN[v] == 0:
            q = [v]
    count = 0
    while q:
        v = q.pop()
        n[v] =  count
        count += 1
        for u in E_from[v]:
            IN[u] -= 1
            if IN[u] == 0:
                q.append(u)
    return n
import heapq
n,m = map(int,input().split())
edge_from = [[] for _ in range(n)]
edge_in = [[] for _ in range(n)]
E = []
for i in range(n+m-1):
    go,to = map(int,input().split())
    go -= 1
    to -= 1
    E.append([go,to])
    edge_from[go].append(to)
    edge_in[to].append(go)
res = topological_sort(n,edge_from,edge_in)
rev = [0]*n
for i in range(n):
    rev[res[i]] = i
reve_from = [[] for _ in range(n)]
reve_in = [[] for _ in range(n)]
for go,to in E:
    resgo = res[go]
    resto = res[to]
    heapq.heappush(reve_from[resgo],-resto)
    heapq.heappush(reve_in[resto],-resgo)
ans = [-1]*n
for i in range(n):
    ans[rev[i]] = rev[-reve_in[i][0]] + 1 if reve_in[i] else 0
for i in ans:
    print(i)

Solution (Python):

import sys
sys.setrecursionlimit(100000)
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, ts, used):
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t, ts, used)
    ts.append(s)


def tsort():
    ts = []
    used = [False] * N
    for i in range(N):
        dfs(i, ts, used)
    return ts[::-1]


ts = tsort()
mp = {x: i for i, x in enumerate(ts)}

ans = [None] * N
for t in tsort():
    ans[t] = ts[max(mp[s] for s in rg[t])] + 1 if rg[t] else 0

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

Solution (Python):
import sys
from collections import deque

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
in_counts = [0] * n
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    in_counts[b] += 1

root = 0
for v, ic in enumerate(in_counts):
    if ic == 0:
        root = v
        break

parents = [-1] * n
q = deque([(c, root) for c in links[root]])

while q:
    v, p = q.popleft()
    in_counts[v] -= 1
    if in_counts[v] == 0:
        parents[v] = p
        q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in parents))

Solution (Python):

import sys
sys.setrecursionlimit(100000)
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)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
from collections import deque

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]
IN = [0] * (n+1)

for a, b in A:
    T[a].append(b)
    RT[b].append(a)
    IN[b] += 1

P = [0] * (n+1)

def bfs(v):
    q = deque()
    q.append(v)
    P[v] = 0
    while q:
        v = q.pop()
        for t in T[v]:
            IN[t] -= 1
            if IN[t] == 0:
                P[t] = v
                q.append(t)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

bfs(root(1))
for p in P[1:]:
    print(p)

Solution (Python):
import sys
import heapq
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
kazu = [0]*n
for i in range(n):
        kazu[i] = len(g2[i])
ans = [0] * n
def dfs(x):
        z = []
        for i in g[x]:
                kazu[i]-=1
                if kazu[i] == 0:
                        z.append(i)
                        ans[i] = x+1
        for i in z:
                dfs(i)
dfs(ne)
for i in ans:
        print(i)

Solution (Python):
from collections import defaultdict, deque
import heapq
v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(v+n-1)]

outs = defaultdict(list)
ins = defaultdict(int)
edge_from = [[] for _ in range(v+1)]
edge_to = [[] for _ in range(v+1)]
ans = [-1]*(v+1)
for v1, v2 in es:
    edge_from[v1].append(v2)
    edge_to[v2].append(v1)
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
rev = [0]*(v+1)
for i in range(1,v+1):
    rev[res[i]] = i
redge_to = [[] for _ in range(v+1)]
for i in range(1,v+1):
    for j in edge_to[i]:
        ri = rev[i]
        rj = rev[j]
        heapq.heappush(redge_to[ri],-rj)
for ri in range(1,v+1):
    if redge_to[ri]:
        rj = redge_to[ri][0]
        i = res[ri]
        j = res[-rj]
        ans[i] = j
    else:
        i =res[ri]
        ans[i] = 0
for i in ans[1:]:
    print(i)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]
IN = [0] * (n+1)

for a, b in A:
    T[a].append(b)
    RT[b].append(a)
    IN[b] += 1

P = [0] * (n+1)
used = [0] * (n+1)

def dfs(p, i):
    if used[i]:
        return None
    P[i] = p
    used[i] = True
    for t in T[i]:
        IN[t] -= 1
    for t in T[i]:
        if IN[t] == 0:
            dfs(i, t)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1))
for p in P[1:]:
    print(p)

Solution (Python):
from collections import defaultdict, deque
import heapq
v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(v+n-1)]

outs = defaultdict(list)
ins = defaultdict(int)
edge_from = [[] for _ in range(v+1)]
edge_to = [[] for _ in range(v+1)]
ans = [-1]*(v+1)
for v1, v2 in es:
    edge_from[v1].append(v2)
    edge_to[v2].append(v1)
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
rev = [0]*(v+1)
for i in range(1,v+1):
    rev[res[i]] = i
redge_to = [[] for _ in range(v+1)]
for i in range(1,v+1):
    for j in edge_to[i]:
        ri = rev[i]
        rj = rev[j]
        heapq.heappush(redge_to[ri],-rj)
for ri in range(1,v+1):
    if redge_to[ri]:
        rj = redge_to[ri][0]
        i = res[ri]
        j = res[-rj]
        ans[i] = j
    else:
        i =res[ri]
        ans[i] = 0
for i in ans[1:]:
    print(i)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]
IN = [0] * (n+1)

for a, b in A:
    T[a].append(b)
    RT[b].append(a)
    IN[b] += 1

D = [0] * (n+1)
P = [0] * (n+1)
used = [0] * (n+1)

def dfs(p, i, depth):
    if used[i]:
        return None
    D[i] = depth
    P[i] = p
    used[i] = True
    for t in tuple(T[i]):
        IN[t] -= 1
    for t in tuple(T[i]):
        if IN[t] == 0:
            dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)