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:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque

N, M = map(int, input().split())
G = [[] for i in range(N)]
P = [-2] * N
deg_in = [0] * N


def bfs(s):
    P[s] = -1
    q = deque()
    q.append(s)

    while len(q):
        u = q.popleft()
        for v in G[u]:
            deg_in[v] -= 1
            if deg_in[v] == 0:
                P[v] = u
                q.append(v)


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

    root = -1
    for i in range(N):
        if not deg_in[i]:
            root = i
            break

    bfs(root)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = -1
    index = -1
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = index

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
v = N
n = N+M-1
es = [[int(x)-1 for x in input().split()] for _ in range(n)]
or_cop = [[] for i in range(N)]
for e in es:
    or_cop[e[1]].append(e[0])

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)
root=res[0]            
LL = [[res[i],i] for i in range(N)]

LL=sorted(LL,key=lambda x: x[0])

for i in range(N):
    i_max=-1
    pare = -1
    if i==root:
        print(0)
    else:
        for cand in or_cop[i]:
            if LL[cand][1]>i_max:
                i_max=LL[cand][1]
                pare=cand
        print(pare+1)

Submission status: Accepted

Solution code:
# from collections import namedtuple
# Node = namedtuple("Node", "in, out")
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N+M-1)]
ine = [[] * N for _ in range(N)]
oute = [[] * N for _ in range(N)]
for a, b in AB:
    ine[b-1].append(a-1)
    oute[a-1].append(b-1)
root = ine.index([])
v = [len(e) for e in ine]
#print(v)
ans = [0] * N
q = [(root, n) for n in oute[root]]
while q:
    nq = []
    for p, n in q:
        v[n] -= 1
        if v[n] == 0:
            ans[n] = p + 1
            nq += [(n, nn) for nn in oute[n]]
    q = nq

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N,M=map(int,input().split())
G1=[[] for i in range(N)]
G2=[[] for i in range(N)]
not_root=[False]*N
for i in range(N+M-1):
  a,b=map(int,input().split())
  G1[a-1].append(b-1)
  G2[b-1].append(a-1)
  not_root[b-1]=True
for i in range(N):
  if not not_root[i]:
    root=i
    break
Tree=[-2]*N
Tree[root]=-1
def dfs(x):
  for b in G1[x]:
    if Tree[b]>=-1:
      continue
    flag=0
    for a in G2[b]:
      if Tree[a]<-1:
        flag=1
        break
    if flag==0:
      Tree[b]=x
      dfs(b)
dfs(root)
for i in range(N):
  print(Tree[i]+1)

Submission status: Accepted

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

N,M=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1+M)]

CLIST=[[] for i in range(N+1)]
PLIST=[[] for i in range(N+1)]

for x,y in EDGE:
    PLIST[y].append(x)
    CLIST[x].append(y)


ANSLIST=[-1]*(N+1)
check=[0]*(N+1)

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

#check[root]=1
ANSLIST[root]=0

QUE= deque()
QUE.append(root)

while QUE:
    x=QUE.pop()
    
    for next in CLIST[x]:
        count=0
        for j in PLIST[next]:
            if check[j]==1:
                continue
            count+=1
        if count==1:
            QUE.append(next)
            ANSLIST[next]=x
    check[x]=1

for a in ANSLIST[1:]:
    print(a)

Submission status: Accepted

Solution code:
#n,a,b = [int(i) for i in input().split()]
from collections import deque

n,m=[int(i) for i in input().split()]
oya=[[] for i in range(n)]
ko=[[] for i in range(n)]
for i in range(n+m-1):
    aa,bb=[int(i)-1 for i in input().split()]
#    print(aa,bb)
    oya[bb].append(aa)
    ko[aa].append(bb)


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

#print(oya)
#print(ko)

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

#print(oya)
#print(ko)

for i in range(n):
    if oya[i][0] == 'root':
        print(0)
    else:
        print(oya[i][0]+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def read():
    return int(input())


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


def readmap():
    return map(int, input().split())


N, M = readmap()
es = []
for _ in range(N - 1 + M):
    a, b = readmap()
    es.append([a, b])

v = N
n = N - 1 + M
# 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 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)

del res[0]
topo = res
inv_topo = [0] * N
for i in range(1, N+1):
    inv_topo[topo[i-1]-1] = i

parent = [0 for _ in range(N+1)]
for edge in es:
    child = edge[1]
    if parent[child] == 0:
        parent[child] = edge[0]
    else:
        if inv_topo[parent[child] - 1] < inv_topo[edge[0] - 1]:
            parent[child] = edge[0]

del parent[0]
for p in parent:
    print(p)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
oy=[set() for i in range(n+1)]
ko=[set() for i in range(n+1)]
ans= [0 for i in range(n+1)]
for i in range(m+n-1):
  a,b=map(int,input().split())
  oy[b]|={a}
  ko[a]|={b}
  
for i in range(1,len(oy)):
  if oy[i]==set():
    break

l=[[i,ko[i]]]
while l:
  o,k=l.pop()
  for i in k:
    oy[i].remove(o)
    if len(oy[i])==0:
      l.append([i,ko[i]])
      ans[i]=o
for i in ans[1:]:
  print(i)

Submission status: Accepted

Solution code:
import queue
N, M = map(int, input().split())
ParentNum = [None] * N
EdgeFrom = [[] for _ in range(N)]
EdgeTo = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    EdgeFrom[B-1].append(A-1)
    EdgeTo[A-1].append(B-1)

for i in range(N):
    if not EdgeFrom[i]:
        ParentNum[i] = 0
        ParentNode = i
        break

Q = queue.Queue()
Q.put(ParentNode)
while not Q.empty():
    currentNode = Q.get()
    for node in EdgeTo[currentNode]:
        if len(EdgeFrom[node]) > 1:
            EdgeFrom[node].remove(currentNode)
        else:
            ParentNum[node] = currentNode + 1
            Q.put(node)
for item in ParentNum:
    print(item)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
to = [0] * (N+1)
E = [set() for i in range(N+1)]
for i in range(N+M-1):
    A, B = map(int, input().split())
    E[A].add(B)
    #E.append([A, B])
    to[B] += 1
A = [0] * (N+1)
for root, t in enumerate(to[1:], 1):
    if t==0:
        break
Open = {root}

while len(Open)>0:

    root = Open.pop()

    for r in E[root]:
        #print(r)
        to[r]-=1
        if to[r]==0:
            A[r]=root
            Open.add(r)
for a in A[1:]:
    print(a)

Submission status: Accepted

Solution code:
import collections

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

in_graph = [[] for i in range(n)]
out_graph = [[] for i in range(n)]
in_count = [0] * n
out_count = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    out_graph[a].append(b)
    out_count[a] += 1
    in_graph[b].append(a)
    in_count[b] += 1
root = in_count.index(0)
ranks = [0] * n
parent = [0] * n
dq = collections.deque()
for i in range(n):
    if out_count[i] == 0:
        dq.append(i)
rank = n
while dq:
    v = dq.popleft()
    ranks[v] = rank
    rank -= 1
    for nv in in_graph[v]:
        out_count[nv] -= 1
        if out_count[nv] == 0:
            dq.append(nv)

for i in range(n):
    max_v = -1
    max_rank = -1
    for v in in_graph[i]:
        if max_rank < ranks[v]:
            max_rank = ranks[v]
            max_v = v
    print(max_v+1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
for i in range(N-1+M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    H[b-1].append(a-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
tbl=[-1 for i in range(N)]
for i in range(N):
    tbl[res[i]]=i
ans=[0 for i in range(N)]
for i in range(1,N):
    L=[]
    for p in H[res[i]]:
        L.append((tbl[p],p))
    ans[res[i]]=max(L)[1]+1
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter, deque
from bisect import *

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
rem = [0] * N
for i in range(N-1+M):
  a, b = reads()
  edges[a-1].append(b-1)
  rem[b-1] += 1

root = next(i for i in range(N) if rem[i] == 0)

par = [-1] * N
que = deque([root])

while len(que) != 0:
  x = que.popleft()
  for y in edges[x]:
    par[y] = x
    rem[y] -= 1
    if rem[y] == 0:
      que.append(y)

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * (n - 1 + m)))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(n - 1 + m):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        la[x] = j + 1
        j += 2
    st = []
    pu = st.append
    po = st.pop
    col = [None] * (n + 1)
    top = []
    tpu = top.append
    for i in xrange(1, n + 1):
        if col[i] is not None:
            continue
        pu((i, la[i]))
        while st:
            x, y = po()
            if col[x] is None:
                col[x] = 1
            while y is not None and col[dat[y]]:
                y = xt[y]
            if y is None:
                tpu(x)
            else:
                pu((x, xt[y]))
                pu((dat[y], la[dat[y]]))
    rto = [0] * (n + 1)
    for i, x in enumerate(top):
        rto[x] = i
    par = [0] * (n + 1)
    rto[0] = n + 1
    for i in xrange(1, n + 1):
        y = la[i]
        while y is not None:
            z = dat[y]
            if rto[par[z]] > rto[i]:
                par[z] = i
            y = xt[y]
    stdout.write(''.join('%d\n' % x for x in par[1:]))
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

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


# print(P)
# print(C)

dp = [-1] * N
def calc(i):
    if dp[i] >= 0:
        return dp[i]
    if not P[i]:
        dp[i] = 0
        return 0
    ma = -1
    for p in P[i]:
        ma = max(ma, calc(p))
    dp[i] = ma+1
    return ma+1

for i in range(N):
    calc(i)

for i in range(N):
    if dp[i] == 0:
        print(0)
    else:
        for p in P[i]:
            if dp[p] == dp[i] - 1:
                print(p+1)
                break

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(N-1+M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    Lin[b]+=1
    table[a].append(b)
M=[0]*N
H=deque()
s=-1
for i in range(N):
    if Lin[i]==0:
        s=i
        break
H.append(s)
while H:
    x=H.popleft()
    for y in table[x]:
        Lin[y]-=1
        if Lin[y]==0:
            M[y]=x+1
            H.append(y)
print('\n'.join(map(str,M)))

Submission status: Accepted

Solution code:
from collections import deque

readline = open(0).readline
N, M = map(int, readline().split())
deg = [0]*N
G = [[] for i in range(N)]
RG = [[] for i in range(N)]
for i in range(N-1+M):
    a, b = map(int, readline().split())
    deg[b-1] += 1
    G[a-1].append(b-1)
    RG[b-1].append(a-1)

que = deque()
for i in range(N):
    if deg[i] == 0:
        que.append(i)

res = ["0\n"]*N
L = [0]*N
while que:
    v = que.popleft()
    r = 0; x = None
    for w in RG[v]:
        if r < L[w] + 1:
            r = L[w] + 1
            x = w
    if x is not None:
        L[v] = r
        res[v] = "%d\n" % (x+1)
    for w in G[v]:
        deg[w] -= 1
        if deg[w] == 0:
            que.append(w)

open(1, 'w').writelines(res)

Submission status: Accepted

Solution code:
def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())
import heapq

n, m = mi()
g = [[] for i in range(n + 1)]
deg = [0] * (n + 1)
for i in range(n + m - 1):
    u, v = mi()
    g[u].append(v)
    deg[v] += 1

pq = []
for u in range(1, n + 1):
    if deg[u] == 0:
        pq.append((0, u))
par = [0] * (n + 1)
dist = [0] * (n + 1)
while pq:
    d, u = heapq.heappop(pq)
    if d > deg[u]: continue
    for v in g[u]:
        if dist[v] < dist[u] + 1:
            dist[v] = dist[u] + 1
            par[v] = u
        deg[v] -= 1
        heapq.heappush(pq, (deg[v], v))

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    f = collections.defaultdict(set)
    for _ in range(n+m-1):
        a,b = LI_()
        e[a].add(b)
        f[b].add(a)

    s = -1
    for k in e.keys():
        if len(f[k]) == 0:
            s = k
            break

    r = [None] * n
    r[s] = 0
    al = set([s])
    q = set([s])
    while q:
        u = set()
        for c in q:
            for d in e[c]:
                if len(f[d] - al) == 0:
                    u.add(d)
                    r[d] = c + 1
        al |= u
        q = u

    return '\n'.join(map(str, r))



print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, M, UV):
    g = defaultdict(list)
    fin = Counter()
    for u, v in UV:
        g[u].append(v)
        fin[v] += 1

    r = -1
    for v in range(1, N+1):
        n = fin[v]
        if n == 0:
            r = v
            break

    a = defaultdict(lambda: None)
    q = deque([r])
    a[r] = 0
    while q:
        u = q.popleft()
        for v in g[u]
            if a[v] != u:
                a[v] = u
                q.append(v)

    ans = [a[i] for i in range(1, N+1)]
    return ans


def main():
    N, M = read_int_n()
    UV = [read_int_n() for _ in range(N-1+M)]
    print(*slv(N, M, UV), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 
 
def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD
 
 
def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD
 
 
def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret
 
 
def solve():
    n, m = getList()
    iri = [0 for i in range(n)]
    ki = [[] for i in range(n)]
 
    for i in range(n + m - 1):
        a, b = getZList()
        iri[b] += 1
        ki[a].append(b)
 
    root = -1
    for i, ir in enumerate(iri):
        if ir == 0:
            root = i
            break
 
    depth = [0 for i in range(n)]
    oya = [-1 for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root] = 1
    d = deque()
    d.append(root)
    while(d):
        cur = d.pop()
        cd = depth[cur]
        for nx in ki[cur]:
            if depth[nx] < cd + 1:
                depth[nx] = cd + 1
                oya[nx] = cur
 
            if not visited[nx]:
                d.append(nx)
 
            visited[nx] = 1
 
    for oy in oya:
        print(oy + 1)
 
 
 
def main():
    n = getN()
    for _ in range(n):
        solve()
 
 
if __name__ == "__main__":
    # main()
    solve()
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def solve():
    n, m = getList()
    iri = [0 for i in range(n)]
    ki = [[] for i in range(n)]

    for i in range(n + m - 1):
        a, b = getZList()
        iri[b] += 1
        ki[a].append(b)

    root = -1
    for i, ir in enumerate(iri):
        if ir == 0:
            root = i
            break

    depth = [0 for i in range(n)]
    oya = [-1 for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root] = 1
    d = deque()
    d.append(root)
    while(d):
        cur = d.popleft()
        cd = depth[cur]
        for nx in ki[cur]:
            if depth[nx] < cd + 1:
                depth[nx] = cd + 1
                oya[nx] = cur

            if not visited[nx]:
                d.append(nx)

            visited[nx] = 1

    for oy in oya:
        print(oy + 1)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ALL = [i for i in range(N)]
ALL = set(ALL)
Graph = [[] for _ in range(N)]
gyaku = [set([]) for _ in range(N)]
for i in range(N-1+M):
  a,b = map(int,input().split())
  a-=1;b-=1
  Graph[a].append(b)
  gyaku[b].add(a)
  ALL.discard(b)
#print(Graph,gyaku)
ALL = list(ALL);root = ALL[0]

used = set([])
TS = []
def dfs(v):
  if v in used:
    return
  used.add(v)
  for w in Graph[v]:
    if w in used:
      continue
    dfs(w)
    TS.append(w)
    
dfs(root)
TS.append(root)
#TS.reverse()
#print(TS)
ans = [0 for _ in range(N)]
for i in range(N):
  now = TS[i]
  for j in range(i+1,N):
    #print(now,TS[j],gyaku[now])
    if TS[j] in gyaku[now]:
      ans[now] = TS[j]+1 #1index
      break
for x in ans:
  print(x)

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(N-1+M)]

in_out = [[[], []] for i in range(N)]

for edge in edges:
    x, y = edge
    in_out[x-1][1].append(y)
    in_out[y-1][0].append(x)

for i in range(N):
    if len(in_out[i][0]) == 0:
        start = i+1
        break

edge_dict = {}
que = deque([[0, start]])
def bfs(past, now):
    edge_dict[now] = past
    try: 
        x, y = que.popleft()
        for node in in_out[y-1][1]:
            que.append([y, node])
        bfs(x, y)
    except IndexError:
        pass
    

bfs(0, start)
dic = sorted(edge_dict.items())
for edge in dic:
    print(edge[1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i,e in enumerate(edg):
        if len(e) == 1:
            ans[e] = i
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if d[e]:
                    ans[e] = -1
                    edg[i].remove(e)
                    d[e] = 0
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
40 90

Submission status: Runtime Error

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

  for i, m in enumerate(cnt):
    if m==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.append(c)

  ans = '\n'.join(par)
  print(ans)
  
if __name__== '__main__':
  main()

Submission status: Runtime Error

Solution code:
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_out = [[] for _ in range(N + 1)]
e_in = [[] for _ in range(N + 1)]
for _ in range(N + M - 1):
    a, b = map(int, readline().split())
    e_out[a].append(b)
    e_in[b].append(a)


# 1. 入次数が0のやつが親
# 2. 親が決まれば、そのこの入次数を減らす,1に戻る

# 親を決めるよ
for i, e in enumerate(e_in[1:], start=1):
    if len(e) == 0:
        root = i
        break

node = [root]
parent = [-1] * (N + 1)
parent[root] = 0
diff = [0] * (N + 1)  # 入次数をどれだけ減らすか

while node:
    s = node.pop()
    for t in e_out[s]:
        diff[t] += 1
        if len(e_in[t]) - diff[t] == 0:
            parent[t] = s
            node.append(t)

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

Submission status: Runtime Error

Solution code:
import sys
def tsort(g):
  N = len(g)
  L = []
  temp = [False for _ in range(N)]
  perm = [False for _ in range(N)]
  def visit(n):
    if temp[n]:
      return 1
    elif not perm[n]:
      temp[n] = True
      for t in g[n]:
        visit(t)
      perm[n] = True
      temp[n] = False
      L.insert(0, n)
      return 0
  for i in range(N):
    if not perm[i] and not temp[i]:
      t = visit(i)
      if t == 1:
      	return [-1 for _ in range(N)]
  return L

def dfs(g, s):
  N = len(g)
  ret = [-1 for _ in range(N)]
  visited = [False for _ in range(N)]
  def _dfs(v):
    visited[v] = True
    for t in g[v]:
      if not visited[t]:
        ret[t] = v
        _dfs(t)
  _dfs(s)
  return ret

N, M = map(int, input().split())
g = [[] for _ in range(N)]
for _ in range(N+M-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
tsorted = tsort(g)
print(tsorted, file=sys.stderr)
ans = [-1 for _ in range(N)]
for u in tsorted:
  for v in g[u]:
    ans[v] = u
ans = map(lambda x: x+1, ans)
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

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)
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 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: Runtime Error

Solution code:
n,m=map(int,input().split())
edge=[]

for i in range(n-1+m):
    a,b=map(int,input().split())
    edge.append((a-1,b-1))
root=[[] for i in range(n)]
s=[-1]*n
for par,node in edge:
    root[par].append(node)
    s[node]=1
r=-1
d=[-1]*n
for i in range(n):
    if s[i]==-1:
        r=i
        break
d[r]=0
par=[0]*n
def dfs(node,depth):
    for v in root[node]:
        if d[v]==-1:
            par[v]=node
            d[v]=depth+1
            dfs(v,depth+1)
        elif d[v]<depth+1:
            par[v]=node
            d[v]=depth+1
            dfs(v,depth+1)
dfs(r,0)

for i in range(n):
    print(par[i]+1 if par[i]>0 else 0)

Submission status: Runtime Error

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

dep=[-1]*N
def depth(n):
  if dep[n-1]!=-1:
    return dep[n-1]
  else:
    if len(par[n-1])==0:
      dep[n-1]=0
      return 0
    else:
      dep[n-1]=max([depth(i) for i in par[n-1]])+1
      return dep[n-1]

for i in range(N):
  if len(par[i])==0:
    print(0)
  elif len(par[i])==1:
    print(par[i][0])
  else:
    m=-1
    a=par[i][0]
    for j in par[i]:
      d=depth(j)
      if m<d:
        m=d
        a=j
    print(a)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

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

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
ans = [-1] * N

# 葉からの検索を行う
@lru_cache(maxsize=None)
def search(now):
    if now == root:
        ans[now] = 0
        return 0
    ret = -1
    for pr in parent[now]:
        depth = search(pr)
        if depth > ret:
            ans[now] = pr + 1
            ret = depth
    return ret + 1

for i in range(N):
    search(i)

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