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 = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n, m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
pps = [set() for _ in range(n)]
for i in range(n-1+m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    pps[b].add(a)

for i,s in enumerate(pps):
    if not s:
        r = i
        
def tps(start):
    q = [start]
    # 行きがけ順
    seen = [None] * n
    # 帰りがけ順
    done = [None] * n
    d0 = 0
    d1 = n
    seen[start] = d0
    while q:
        u = q.pop()
        if u>=0:
            q.append(~u)
            for v in ns[u]:
                if done[v] is None:
                    d0 += 1
                    seen[v] = d0
                    q.append(v)
        else:
            d1 -= 1
            done[~u] = d1
    return seen, done

done = [None]*n
seen = [False]*n
def dfs(u, val):
    for v in ns[u]:
        if seen[v]:
            continue
        seen[v] = True
        val = dfs(v, val)
    val = val - 1
    done[u] = val
    return val

dfs(r, n)
# seen, done = tps(r)
ps = [-1] * n
ps[r] = 0
for i in range(n):
    if i==r:
        continue
    val = max(pps[i], key=lambda item: done[item])
    ps[i] = val+1
write("\n".join(map(str, ps)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
pps = [set() for _ in range(n)]
for i in range(n-1+m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    pps[b].add(a)

for i,s in enumerate(pps):
    if not s:
        r = i
        
def tps(start):
    q = [start]
    # 行きがけ順
    seen = [None] * n
    # 帰りがけ順
    done = [None] * n
    d0 = 0
    d1 = n
    seen[start] = d0
    while q:
        u = q.pop()
        if u>=0:
            q.append(~u)
            for v in ns[u]:
                if seen[v] is None:
                    d0 += 1
                    seen[v] = d0
                    q.append(v)
        else:
            d1 -= 1
            done[~u] = d1            
    return seen, done

done = [None]*n
val = n
def dfs(u, val):
    for v in ns[u]:
        if done[v] is not None:
            continue
        val = dfs(v, val)
    val = val - 1
    done[u] = val
    return val

# seen, done = tps(r)
dfs(r, n)
ps = [-1] * n
ps[r] = 0
for i in range(n):
    if i==r:
        continue
    val = max(pps[i], key=lambda item: done[item])
    ps[i] = val+1
write("\n".join(map(str, ps)))

Submission status: Accepted

Solution code:
from collections import deque

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)
            self.rev[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[1] - indexed] += 1

    def topological_sort(self):
        deg = self.deg[:]
        res = [i for i in range(self.n) if deg[i] == 0]
        queue = deque(res)
        used = [False for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                deg[adj] -= 1
                if deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res

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

g = Graph(N, E)
ts = g.topological_sort()
node_to_ts = [0 for _ in range(N)]

for i in range(N):
    node_to_ts[ts[i]] = i

for i in range(N):
    tmp = -1
    res = -1
    for j in g.rev[i]:
        if tmp < node_to_ts[j]:
            tmp = node_to_ts[j]
            res = j
    print(res + 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from collections import deque,defaultdict,Counter
def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M + N - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        deg[b] += 1
        G[a].append(b)
    
    ans = [-1] * N
    for i in range(N):
        if deg[i] == 0:
            root = i
            ans[root] = 0
            break
    
    q = deque([root])
    while q:
        v = q.popleft()
        for e in G[v]:
            deg[e] -= 1
            if deg[e] == 0:
                ans[e] = v + 1
                q.append(e)
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(N-1+M)]
graph = [[] for _ in range(N)]
d_in = [0]*N
for a, b in AB:
	a, b = a-1, b-1
	graph[a].append(b)
	d_in[b] += 1

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

ans = [None]*N
ans[root] = 0
q = deque([root])
while q:
	n = q.popleft()
	for node in graph[n]:
		d_in[node] -= 1
		if d_in[node] == 0:
			ans[node] = n+1
			q.append(node)

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

Submission status: Accepted

Solution code:
# # E - League
# https://atcoder.jp/contests/abc139/tasks/abc139_e

# トポロジカルソート　トポソ

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)]

outs = defaultdict(list)
rev = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1 - 1].append(v2 - 1)
    rev[v2 - 1].append(v1 - 1)
    ins[v2 - 1] += 1

q = deque(v1 for v1 in range(n) 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)

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

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
pbuf = [[] for i in range(n)]
counts = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
        edges.pop(p)
    else:
        nex = []
    for n in nex:
        counts[n-1] += 1
        if counts[n-1] == ins[n-1]:
            parent[n-1] = p
            que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n+m-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in e[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in e[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t
top=find_loop(n,edge,1)
d=[0]*n
for i in range(n):
  for j in edge[top[i]]:d[j]=d[top[i]]+1
ans=[-1]*n
ans[d.index(0)]=0
for i in range(n):
  for j in edge[i]:
    if d[i]+1==d[j]:ans[j]=i+1
print(*ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
es=[[] for i in range(n)]
deg=[0]*n
for i in range(n-1+m):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    deg[b-1]+=1

ans=[]
from collections import deque
que=deque([])
for i in range(n):
    if deg[i]==0:
        que.append((i,-1))

while que:
    s=que.pop()
    ans.append(s)
    for e in es[s[0]]:
        deg[e]-=1
        if deg[e]==0:
            que.append((e,s[0]))
ans=sorted(ans)
for i in range(n):
    print(ans[i][1]+1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
es=[[] for i in range(n)]
deg=[0]*n
for i in range(n-1+m):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    deg[b-1]+=1

ans=[]
from collections import deque
que=deque([])
for i in range(n):
    if deg[i]==0:
        que.append((i,-1))

while que:
    s=que.popleft()
    ans.append(s)
    for e in es[s[0]]:
        deg[e]-=1
        if deg[e]==0:
            que.append((e,s[0]))
ans=sorted(ans)
for i in range(n):
    print(ans[i][1]+1)

Submission status: Accepted

Solution code:
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
que = deque(v1 for v1 in range(n) if ins[v1]==0)
res = []
par = [0]*(n+1)
while que:
    v1 = que.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2]==0:
            que.append(v2)
            par[v2] = v1
for p in par[1:]:
  print(p)

Submission status: Accepted

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

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

for i in range(1, N+1):
  if num_in[i] == 0:
    root = i
    break

par = [-1] * (N+1)
par[root] = 0
d = [root]
while d:
  node = d.pop()
  children = graph[node]
  for child in children:
    num_in[child] -= 1
    if num_in[child] == 0:
      par[child] = node
      d.append(child)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    inv[b - 1] += 1
for i in range(n):
    if inv[i] == 0:
        root = i
        break
d = [0] * n
s = [root]
while s:
    p = s.pop()
    for node in g[p]:
        inv[node] -= 1
        if inv[node] == 0:
            d[node] = max(d[node], d[p] + 1)
            s.append(node)
ans = [0] * n
for i in range(n):
    for node in g[i]:
        if d[node] == d[i] + 1:
            ans[node] = i + 1
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import queue
def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    par = [None]*(n+1)
    cnt = [0]*(n+1)
    for _ in range(n-1+m):
        a, b = map(int, input().split())
        G[a].append(b)
        cnt[b] += 1
    p = -1
    for i in range(1, n+1):
        if cnt[i] == 0:
            p = i
            break
    par[p] = 0
    q = queue.Queue()
    q.put(p)
    t = [0]*(n+1)
    while not q.empty():
        x = q.get()
        for v in G[x]:
            t[v] += 1
            if t[v] == cnt[v]:
                q.put(v)
            par[v] = x
    for ans in par[1:]:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import deque, defaultdict
    N, M = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(N + M - 1)]
    in_cnt = defaultdict(int)
    outs = defaultdict(list)
    for a, b in ab:
        in_cnt[b - 1] += 1
        outs[a - 1].append(b - 1)
    res = []
    queue = deque([i for i in range(N) if in_cnt[i] == 0])
    while len(queue) != 0:
        v = queue.popleft()
        res.append(v)
        for v2 in outs[v]:
            in_cnt[v2] -= 1
            if in_cnt[v2] == 0:
                queue.append(v2)
    dp = [(0, -1)] * N
    for i in res:
        for j in outs[i]:
            if dp[i][0] + 1 > dp[j][0]:
                dp[j] = (dp[i][0] + 1, i)
    for _, i in dp:
        print(i + 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# トポロジカルソート

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
revG = [[] for i in range(N)]
# ある頂点に対する入次数を記録
indegree = [0 for i in range(N)]

for i in range(N - 1 + M):
  u,v = map(int,readline().split())
  G[u - 1].append(v - 1)
  revG[v - 1].append(u - 1)
  indegree[v - 1] += 1

# トポロジカルソートを格納する
res = []

# 入り次数が0になった頂点を高速に発見するため、隣接する頂点をキューで管理
from collections import deque
q = deque()
for i in range(len(indegree)):
  if indegree[i] == 0:
    q.append(i)

while q:
  # キューの先頭の頂点を取り出す
  v = q.popleft()
  
  # その頂点と隣接する頂点の入次数を減らし、0になったらキューに追加
  for child in G[v]:
    indegree[child] -= 1
    if indegree[child] == 0:
      q.append(child)
      
  # 入り次数が0で且つ隣接する頂点が処理済みとなった頂点をソート配列に追加する
  res.append(v)
  
# インデックスと頂点番号を逆転させたものを作成する
inds = [-1 for i in range(N)]
for i in range(len(res)):
  inds[res[i]] = i
  
# print(inds)
for i in range(len(revG)):
  ans = -1
  maxv = -1
  for parent in revG[i]:
#    print("i",i,"に対する親",parent)
    if inds[parent] > maxv:
      maxv = inds[parent]
      ans = parent
  print(ans + 1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    out_list = [[] for _ in range(n + 1)]
    in_cnt = [0] * (n + 1)
    in_cnt[0] = -1
    for _ in range(n - 1 + m):
        a, b = map(int, sys.stdin.readline().split())
        out_list[a].append(b)
        in_cnt[b] = in_cnt[b] + 1
    root = in_cnt.index(0)
    ans = [0] * (n + 1)
    que = deque([root])

    while que:
        p = que.popleft()
        for i in out_list[p]:
            in_cnt[i] = in_cnt[i] - 1
            if in_cnt[i] == 0:
                que.append(i)
                ans[i] = p

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    out_list = defaultdict(list)
    in_cnt = defaultdict(int)
    for _ in range(n - 1 + m):
        a, b = map(int, sys.stdin.readline().split())
        out_list[a].append(b)
        in_cnt[b] = in_cnt[b] + 1
    ans = [0] * (n + 1)
    que = deque([i for i in range(n) if in_cnt[i] == 0])

    while que:
        p = que.popleft()
        for i in out_list[p]:
            in_cnt[i] = in_cnt[i] - 1
            if in_cnt[i] == 0:
                que.append(i)
                ans[i] = p

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    out_list = [[] for _ in range(n + 1)]
    in_cnt = [0] * (n + 1)
    in_cnt[0] = -1
    for _ in range(n - 1 + m):
        a, b = map(int, sys.stdin.readline().split())
        out_list[a].append(b)
        in_cnt[b] = in_cnt[b] + 1
    root = in_cnt.index(0)
    ans = [0] * (n + 1)
    que = deque([])
    que.append(root)

    while que:
        p = que.popleft()
        for i in out_list[p]:
            in_cnt[i] = in_cnt[i] - 1
            if in_cnt[i] == 0:
                que.append(i)
                ans[i] = p

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    from collections import deque
    input = sys.stdin.readline
    n,m = map(int,input().split())
    edge = [[] for i in range(n)]
    edgecnt=[0]*n
    ans=[0]*n
    for i in range(n+m-1):
        a,b= map(int,input().split())
        edge[a-1].append(b-1)
        edgecnt[b-1]+=1
    for i,j in enumerate(edgecnt):
        if j==0:
            ans[i]=-1
            chkedge=deque([i])
            break
    while chkedge:
        chk=chkedge.popleft()
        for i in edge[chk]:
            edgecnt[i]-=1
            if edgecnt[i]==0:
                ans[i]=chk
                chkedge.append(i)
    for i in ans:print(i+1)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
INF = 10 ** 15
MOD = 10 ** 9 + 7 
from collections import deque

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    G_inv = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(N + M - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        deg[b] += 1
        G[a].append(b)
        G_inv[b].append(a)
    for i in range(N):
        if deg[i] == 0:
            root = i
            break
    
    q = deque([root])
    dist = [0] * N
    while q:
        v = q.popleft()
        for e in G[v]:
            dist[e] = dist[v] + 1
            deg[e] -= 1
            if deg[e] == 0:
                q.append(e)

    parents = [0] * N
    for i in range(N):
        if i == root:
            continue
        for e in G_inv[i]:
            if dist[e]  + 1 == dist[i]:
                parents[i] = e + 1
                break

    print('\n'.join(map(str,parents)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
v,n=map(int,input().split())
es=[]
l=[[]for i in range(v)]
for i in range(n-1+v):
    a,b=[int(j)-1 for j in input().split()]
    es.append((a,b))
    l[a].append(b)
#頂点は0~v-1

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 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)

ans=[0]*v
s=set()
for i in res[::-1]:
    s.add(i)
    for j in l[i]:
        if j in s:
            ans[j]=i+1
            s.remove(j)

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
n,m=map(int,input().split())
s=set()
edge=[[] for _ in range(n)]
edgerev=[[] for _ in range(n)]
for _ in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edgerev[b].append(a)
    s.add(b)
for i in range(n):
    if i not in s:
        root=i
        break
visited=[False]*n
to=[] #topological order
def dfs(root):
    if visited[root]:
        return
    visited[root]=True
    for i in edge[root]:
        dfs(i)
    to.append(root)
dfs(root)
to=to[::-1]
#print(to)
result=[0]*n
for i in range(n):
    result[to[i]]=i #頂点の順番
#print(result)
#print(edgerev)
for i in range(n):
    if not edgerev[i]:
        print(0)
        continue
    order=-1
    for j in edgerev[i]:
        if order<result[j]:
            ans=j
            order=result[j]
    print(ans+1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def main():
    N, M = MI()
    edges = []

    for i in range(N-1+M):
        a, b = MI()
        edges.append((a-1, b-1))

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

    res = [0] * N
    queue = deque([i for i in range(N) if in_cnt[i] == 0])
    while len(queue) > 0:
        v = queue.popleft()
        # print(v + 1)
        # res.append(v)
        for nxt_v in outs[v]:
            # print('v', v + 1, 'nxt_v', nxt_v + 1)
            in_cnt[nxt_v] -= 1
            if in_cnt[nxt_v] == 0:
                res[nxt_v] = v + 1
                # print(res, nxt_v + 1, 'p', v + 1)
                queue.append(nxt_v)
    print(*res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, parent_g: {}, v: int, p: int, depth: int, dd: {}, dq):
    p_ls = parent_g.setdefault(v, [])
    if len(p_ls) > 1:
        p_ls.remove(p)
        return
    dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 探索キューに追加
        dq.append((next_v, v, depth+1))


def main():
    n, m = map(int, input().split())

    children = set()
    g = {}
    parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        dic_b = parent_g.setdefault(b - 1, [])
        dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}

    dq = collections.deque()
    dq.append((root, parent, depth))
    while len(dq) > 0:
        t, p, d = dq.popleft()
        bfs(g, parent_g, t, p, d, dd, dq)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M = map(int, rl().split())
    graph = [[] for _ in range(N)]
    indegrees = defaultdict(int)
    for _ in range(N - 1 + M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        indegrees[b] += 1
    
    que = deque([])
    for i in range(N):
        if indegrees[i] == 0:
            que.append(i)
    
    ans = [0] * N
    while que:
        idx = que.pop()
        for child in graph[idx]:
            indegrees[child] -= 1
            if indegrees[child] == 0:
                que.append(child)
                ans[child] = idx + 1
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

    par = [None] * n
    stack = [(v, -1) for v in range(n) if indeg[v] == 0] # 仮定より indeg[v] == 0 の元が1つだけ存在
    while stack:
        v, p = stack.pop()
        par[v] = p
        for nv in E[v]:
            indeg[nv] -= 1
            if indeg[nv] == 0:
                stack.append((nv, v))

    for v in range(n):
        print(par[v] + 1)
resolve()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, M = read_values()

    L = [set() for _ in range(N)]
    C = [0] * N
    S = {i for i in range(N)}
    for _ in range(N + M - 1):
        u, v = read_index()
        L[u].add(v)
        C[v] += 1
        if v in S:
            S.remove(v)

    Q = queue.Queue()
    for s in S:
        Q.put(s)

    P = ["0"] * N    
    while not Q.empty():
        s = Q.get()
        for w in L[s]:
            P[w] = str(s + 1)
            C[w] -= 1
            if C[w] == 0:
                Q.put(w)

    print("\n".join(P))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
child = [set() for _ in range(n)]
parent = [set() for _ in range(n)]
root = set(range(n))

for i in range(n+m-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    parent[b].add(a)
    child[a].add(b)
    if b in root:root.remove(b)

root = list(root)[0]
parent[root].add(-1)

que = deque([root])
d = [[-1,-1] for _ in range(n)]
d[root] = [0,-1]
while que:
    p = que.popleft()
    for nxt in child[p]:
        if d[nxt][1] == -1:
            d[nxt] = [d[p][0] + 1,p]
        elif d[nxt][0] > d[p][0] + 1:
            parent[nxt].remove(p)
        else:
            parent[nxt].remove(d[nxt][1])
            d[nxt][0] = d[p][0] + 1
            d[nxt][1] = p
        if len(parent[nxt]) == 1:
            que.append(nxt)
for i in parent:
    print(list(i)[0] + 1)

Submission status: Accepted

Solution code:
# V: 頂点数
# g[v] = [w, ...]:
#    有向グラフ上の頂点vから到達できる頂点w
# deg[v]:
#    頂点vに到達できる頂点の数

n,m = map(int, input().split())
V,E = n, n-1+m
g = [[] for i in range(V)]
u = [[] for i in range(V)]
deg = [0]*V
for i in range(E):
    s, t = map(int, input().split())
    s-=1
    t-=1
    g[s].append(t)
    u[t].append(s)
    deg[t] += 1

from collections import deque
ans = list(v for v in range(V) if deg[v]==0)
deq = deque(ans)
used = [0]*V

while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)

# ans: トポロジカル順序に並べた頂点

nrank = dict((n, r) for r, n in enumerate(ans))

for i in range(n):
    r = 0
    if u[i]:
        r = sorted(u[i], key=lambda x:-nrank[x])[0]
        print(r+1)
    else:
        print(0)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
n,m=map(int,input().split())
ab = [[int(x) for x in input().split()] for _ in range(n-1+m)]
outs = defaultdict(list)
ins = defaultdict(int)

for v1,v2 in ab:
    outs[v1].append(v2)
    ins[v2]+=1 
ans=[0]*(n+1)
q=deque(int(x) for x in range(n) if ins[x] == 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)
            ans[v2]=v1

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

Submission status: Accepted

Solution code:
from collections import deque

N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(N-1+M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append(i)
queue = deque(topo[:])
topo = [[0,topo[0]]]
while queue:
    n1 = queue.popleft()
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append([n1,n2])
            queue.append(n2)
topo.sort(key=lambda x:x[1])
for i,v in topo:
    print(i)
#  visited = [False for _ in range(N)]

#  ans = 0
#  path_len = 0
#  def dfs(node,cnt=1):
    #  global ans
    #  if visited[node-1]: return 0
    #  visited[node-1] = True
    #  ans = max(ans,cnt)
    #  for n in ad_list[node]:
        #  dfs(n,cnt+1)

#  for n in range(1,N+1):
    #  dfs(n)
#  print(ans)