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



Sample input:
3 1
1 2
1 3
2 3


Sample output:
0
1
2

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    ind = [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)
        ind[b] += 1

    from collections import deque
    q = deque([])
    order = []
    par = [0]*n
    for i in range(n):
        if ind[i] == 0:
            q.append(i)
    while q:
        v = q.popleft()
        order.append(v)
        for u in g[v]:
            ind[u] -= 1
            if ind[u] == 0:
                par[u] = v+1
                q.append(u)
    print(*par, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, M = in_nn()

    dim = [0] * N
    edge = [set() for _ in range(N)]
    for i in range(N + M - 1):
        x, y = in_nn()
        x, y = x - 1, y - 1
        dim[y] += 1
        edge[x].add(y)

    root = dim.index(0)
    q = deque()
    q.append(root)

    while q:
        v = q.popleft()
        delete = set()
        for nv in edge[v]:
            if dim[nv] > 1:
                dim[nv] -= 1
                delete.add(nv)
            else:
                q.append(nv)
        edge[v] -= delete

    ans = [-1] * N

    for v1 in range(N):
        for v2 in edge[v1]:
            ans[v2] = v1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())

outs = [[] for _ in range(N+1)]
outs_rev = [[] for _ in range(N+1)]
ins = [0]*(N+1)
for _ in range(N+M-1):
  v1,v2=map(int,input().split())
  outs[v1].append(v2)
  outs_rev[v2].append(v1)
  ins[v2] += 1
#print(outs,ins)
#print(outs_rev)

q = deque(v1 for v1 in range(N+1) 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)
#print(res)

res_rev=[0]*(N+1)
for i in range(N):
  res_rev[res[i]]=i
#print(res_rev)

answer_list=[0]*(N+1)
for i in range(1,N+1):
  r=res[i]
  if not outs_rev[r]:
    answer_list[r]=0
  else:
    max_v=-1
    max_index=-1
    for rr in outs_rev[r]:
      ind=res_rev[rr]
      if ind>max_index:
        max_v=res[ind]
        max_index=ind
  
    answer_list[r]=max_v
    
#print(answer_list)
for i in range(1,N+1):
  print(answer_list[i])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N,M=map(int,input().split())

outs = defaultdict(list)
outs_rev = defaultdict(list)
ins = defaultdict(int)
for _ in range(N+M-1):
  v1,v2=map(int,input().split())
  outs[v1].append(v2)
  outs_rev[v2].append(v1)
  ins[v2] += 1
#print(outs,ins)
#print(outs_rev)

q = deque(v1 for v1 in range(1,N+1) 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)
#print(res)

res_rev=[0]*N
for i in range(N):
  res_rev[res[i]-1]=i
#print(res_rev)

answer_list=[0]*N
for i in range(N):
  r=res[i]
  if not outs_rev[r]:
    answer_list[r-1]=0
  else:
    max_v=-1
    max_index=-1
    for rr in outs_rev[r]:
      ind=res_rev[rr-1]
      if ind>max_index:
        max_v=res[ind]
        max_index=ind
  
    answer_list[r-1]=max_v
    
#print(answer_list)
for ans in answer_list:
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

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

r=cnt.index(0)
D=[0]*n
q=deque([r])
ans=[0]*n
while q:
    u=q.popleft()
    for v in G[u]:
        cnt[v]-=1
        ans[v] = u + 1
        if not cnt[v]:
            q+=[v]


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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
edge = [[] for i in range(n)]
cnt = [0] * n
ans = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    cnt[b - 1] += 1
Q = deque([cnt.index(0)])
while Q:
    p = Q.popleft()
    for u in edge[p]:
        cnt[u] -= 1
        if cnt[u] == 0:
            ans[u] = p + 1
            Q.append(u)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1+M)]

es = [[] for _ in range(N)]
indeg = [0] * N
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    indeg[b] += 1

from collections import deque
q = deque()
for i in range(N):
    if indeg[i] == 0:
        q.append(i)

ans = [0] * N
while q:
    v = q.popleft()
    for to in es[v]:
        indeg[to] -= 1
        if indeg[to] == 0:
            q.append(to)
            ans[to] = v+1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict
    n, m = map(int, readline().split())
    edge_to = defaultdict(set)
    edge_from = defaultdict(set)
    from_cnt = [0] * n
    par = [-1] * n

    for _ in range(n + m - 1):
        a, b = map(int, readline().split())
        a, b = a - 1, b - 1
        edge_to[a].add(b)
        edge_from[b].add(a)
        from_cnt[b] += 1

    root = from_cnt.index(0)
    par[root] = 0

    que = deque()
    que.append(root)

    while que:
        cur = que.popleft()
        for nx in edge_to[cur]:
            if from_cnt[nx] == 1:
                par[nx] = cur + 1
                que.append(nx)
            else:
                from_cnt[nx] -= 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m = map(int,ipt().split())
    go = [[] for i in range(n+1)]
    cm = [[] for i in range(n+1)]
    for i in range(n+m-1):
        a,b = map(int,ipt().split())
        cm[b].append(a)
        go[a].append(b)

    prnt = [-1]*(n+1)
    q = queue.Queue()
    for i in range(1,n+1):
        if not cm[i]:
            prnt[i] = 0
            for j in go[i]:
                q.put((j,i))
            break

    while not q.empty():
        qn,qp = q.get()
#        print(qn,qp)
        f = True
        for i in cm[qn]:
            if prnt[i] == -1 or prnt[i] == qp:
                f = False
                break

        if f:
            prnt[qn] = qp
            for i in go[qn]:
                q.put((i,qn))

    for i in prnt[1::]:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def topological(N, LIST): #トポロジカルソート:DAGに適用可
    incnt = [0] * N
    CHILD = [set() for _ in range(N)]
    for a, b in LIST:
        CHILD[a - 1].add(b - 1)
        incnt[b - 1] += 1
    
    TPLGSORT = []
    que = deque([i for i, num in enumerate(incnt) if num == 0])
    while len(que) > 0:
        q = que.popleft()
        for i in CHILD[q]:
            incnt[i] -= 1
            if incnt[i] == 0:
                que.append(i)
        TPLGSORT.append(q)
    return TPLGSORT, CHILD


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

tplg, child = topological(n, ab)
ans = [0] * n
for i in tplg:
    for j in child[i]:
        ans[j] = i + 1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    edge = [[] for _ in range(n)]
    edge_r = [[] for _ in range(n)]
    for _ in range(n - 1 + m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge_r[b - 1].append(a - 1)

    visited = [False] * n
    visited[0] = True
    que = deque([0])
    while que:
        v = que.popleft()
        if len(edge_r[v]) == 0:
            root = v
            break
        for u in edge_r[v]:
            if not visited[u]:
                visited[u] = True
                que.appendleft(u)

    cnt = [len(edge_r[i]) for i in range(n)]
    res = [[] for _ in range(n)]
    res[root].append(0)
    que = deque([root])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if cnt[u] > 1:
                cnt[u] -= 1
            else:
                cnt[u] = 0
                que.appendleft(u)
                res[u].append(v + 1)

    for i in res:
        print(*i)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    parcount = [-1]*n
    for i in range(n+m-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        parcount[b-1] += 1
    
    for i in range(n):
        if parcount[i] == -1:
            root = i
            break
    
    par = [0]*n
    dist = [0]*n
    not_yet = deque([root])
    while not_yet:
        key = not_yet.popleft()
        for v in tree[key]:
            if parcount[v]:
                parcount[v] -= 1
                continue
            par[v] = key+1
            dist[v] = dist[key]+1
            not_yet.append(v)
    
    for p in par:
        print(p)
 
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
check = [0 for _ in range(n)]
edges = [[] for _ in range(n)]

for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    check[b - 1] += 1
    edges[a - 1].append(b - 1)

rood = check.index(0)
queue = deque()
ans = [0 for _ in range(n)]
queue.append(rood)
while queue:
    pos = queue.popleft()
    for n_pos in edges[pos]:
        check[n_pos] -= 1
        if check[n_pos] == 0:
            queue.append(n_pos)
            ans[n_pos] = pos + 1
        
for pos in ans:
    print(pos)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lis=[tuple(map(int,input().split()))for _ in range(n+m-1)]
node_in=[0]*n
node=[[]for i in range(n)]
for x,y in lis:
	node_in[y-1]+=1
	node[x-1].append(y-1)
for i in range(n):
	if node_in[i]==0:
		root=i
		break
ans=[-1]*n
ans[root]=0
stack=[root]
while stack:
	r=stack.pop()
	for x in node[r]:
		node_in[x]-=1
		if node_in[x]==0:
			stack.append(x)
			ans[x]=r+1
for x in ans:
	print(x)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    prnt_cnt = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        prnt_cnt[b] += 1

    root_idx = prnt_cnt.index(0)

    que = collections.deque([root_idx])

    while que:
        q = que.popleft()
        for ei in e[q]:
            prnt_cnt[ei] -= 1
            if prnt_cnt[ei] == 0:
                ans[ei] = q
                que.append(ei)

    for ansi in ans:
        print(ansi + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    root = [True for _ in range(n)]
    prnt_cnt = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        root[b] = False
        prnt_cnt[b] += 1

    root_idx = root.index(True)

    que = collections.deque([root_idx])

    while que:
        q = que.popleft()

        for ei in e[q]:
            ans[ei] = q
            prnt_cnt[ei] -= 1
            if prnt_cnt[ei] == 0:
                que.append(ei)

    for ansi in ans:
        print(ansi + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

graph = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
in_degree = [0] * n
out_degree = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph2[b].append(a)
    in_degree[b] += 1
    out_degree[a] += 1

v_root = in_degree.index(0)

depth = [-1] * n
ans = [0] * n
depth[v_root] = 0


def dfs(v):
    if depth[v] == -1:
        for v_par in graph2[v]:
            d = dfs(v_par)
            if depth[v] < d + 1:
                depth[v] = d + 1
                ans[v] = v_par + 1
    return depth[v]


for i in range(n):
    if out_degree[i] == 0:
        # print(i)
        _ = dfs(i)

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
T,F=[[]for i in range(N)],[[]for i in range(N)]
for i in range(N-1+M):
  a,b=map(int, input().split())
  a-=1
  b-=1
  T[a].append(b)
  F[b].append(a)
  
for i in range(N):
  if len(F[i])==0:
    R=i
    break
    
ans=[-1]*N
ans[R]=0

from collections import deque
q=deque([])
q.append(R)
s=set()
while q:
  now=q.popleft()
  s.add(now)
  for i in T[now]:
    if ans[i]==-1:
      c=0
      for j in F[i]:
        if j not in s:
          c=1
          break
      if c==0:
        ans[i]=now+1
        q.append(i)
        
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]

    for i in co[v]:
        x = memo(i) + 1
        if x > dp[v]:
            parent[v] = i + 1
            dp[v] = x

    return max(dp[v], 0)

parent = [0] * n
for i in range(n):
    memo(i)


for i in parent:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]
    a = 0
    for i in co[v]:
        a = max(a, memo(i) + 1)
    dp[v] = a
    return a

for i in range(n):
    memo(i)

parent = [0] * n
for v in range(n):
    for e in es[v]:
        if dp[v] + 1 == dp[e]:
            parent[e] = v + 1

for i in parent:
    print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
def topological_sort(graph):
  N = len(graph)
  in_cnt = [0 for i in range(N)]
  for x in range(N):
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in range(N) if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in range(N) if in_cnt[i]]:
    return None
  return ret

N,M = IL()
graph = [set() for i in range(N)]
graph_from = [set() for i in range(N)]

for i in range(N+M-1):
  a,b = IL()
  graph[a-1].add(b-1)
  graph_from[b-1].add(a-1)
  
dic2 = topological_sort(graph)

dic = [None]*N
for i in range(N):
  dic[dic2[i]] = i

ans = []
for y in range(N):
  d = -1
  p = 0
  for x in graph_from[y]:
    if dic[x] > d:
      d = dic[x]
      p = x+1
  ans.append(p)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
def topological_sort(graph_to, graph_from):
  graph_from_cnt = [len(graph_from[i]) for i in range(N)]
  dic = DD(int)
  q = deque([i for i in range(N) if not graph_from_cnt[i]])
  while q:
    x = q.popleft()
    dic[x] = len(dic)
    for y in graph_to[x]:
      graph_from_cnt[y] -= 1
      if not graph_from_cnt[y]:
        q.append(y)
  return dic

N,M = IL()
graph_to = [set() for i in range(N)]
graph_from = [set() for i in range(N)]
graph_from_cnt = [0 for i in range(N)]

for i in range(N+M-1):
  a,b = IL()
  graph_to[a-1].add(b-1)
  graph_from[b-1].add(a-1)

dic = topological_sort(graph_to, graph_from)

ans = []
for y in range(N):
  d = -1
  p = 0
  for x in graph_from[y]:
    if dic[x] > d:
      d = dic[x]
      p = x+1
  ans.append(p)

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