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:
from collections import defaultdict, deque
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
par =  [0]*N
cnt = [0]*(N+1)
for a,b in zip(*[iter(L)]*2):
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    par[i-1] = '0'
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c-1] = str(m)
      q += [c]

ans = '\n'.join(par)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
par =  [0]*(N+1)
cnt = [0]*(N+1)
for a,b in zip(*[iter(L)]*2):
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c] = m
      q += [c]

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
par =  [0]*(N+1)
cnt = [0]*(N+1)
for i in range(N-1+M):
  a, b = map(int, input().split())
  dic[a] += [b]
  cnt[b] += 1

for i in range(1,N+1):
  if cnt[i]==0:
    q = deque([i])
    break
  
while q:
  m = q.popleft()
  for c in dic[m]:
    cnt[c] -= 1
    if cnt[c]==0:
      par[c] = m
      q += [c]

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
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
    #print(indegree)
    #入次数が0の点からあれしていく
    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(*topological_index,sep="\n")
    print(*ans,sep="\n")    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
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
    #print(indegree)
    #入次数が0の点からあれしていく
    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(*topological_index,sep="\n")
    print(*ans,sep="\n")    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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

# BFS
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")

Submission status: Accepted

Solution code:
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

# BFS
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")

Submission status: Accepted

Solution code:
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

# BFS
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")

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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  # counter for in-degree of vertices
    for i in range(n):
        for j in g[i]:
            indeg[j]+=1
    
    # gather vertices with 0 in-degree
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

    # longest path (topological sort)
    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)

    # 各頂点に対して、逆辺の dp の値の最小が親
    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()

Submission status: Accepted

Solution code:
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)

    # longest path
    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

    # 各頂点に対して、逆辺の dp の値の最小が親
    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()

Submission status: Accepted

Solution code:
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]
#    print(Cnt)
#    print(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()

Submission status: Accepted

Solution code:
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
# MOD = 998244353


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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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}
#L = []
while S:
    n = S.pop()
    #L.append(n)
    for m in out[n]:
        inc[m] -= 1
        if inc[m] == 0:
            S.add(m)
            ans[m] = n + 1 
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)