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: Time Limit Exceeded

Solution code:
import heapq as h
import sys

input=sys.stdin.readline


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

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


parent=[-1 for i in range(0,N)]
q=[]
q.append(root)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in to[x]:
            h.heappush(sub,p)
            parent[p]=x
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

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

Submission status: Time Limit Exceeded

Solution code:
import heapq as h

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

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


parent=[-1 for i in range(0,N)]
q=[]
q.append(root)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in to[x]:
            h.heappush(sub,p)
            parent[p]=x
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()

nl = [list() for _ in range(N + 1)]
rev = [list() for _ in range(N + 1)]
for _ in range(N - 1 + M):
    A, B = MI()
    nl[A].append(B)
    rev[B].append(A)

for i, l in enumerate(rev):
    if i > 0 and len(l) == 0:
        root = i
        break

ans = [-1] * (N + 1)
q = deque([(root, 0)])
while len(q) > 0:
    v, p = q.popleft()
    ans[v] = p
    for next_v in nl[v]:
        q.append((next_v, v))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

# V = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        if x != P[i]:
            # V[x] = 1
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

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

Submission status: Time Limit Exceeded

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
data=[[] for i in range(N+1)]
lst=set()
for a,b in AB:
    data[a].append(b)
    lst.add(b)

st=list(set(range(1,N))-lst)[0]
stack=deque([st])
lst=[0 for i in range(N+1)]
while stack:
    a=stack.popleft()
    for p in data[a]:
        lst[p]=a
        stack.append(p)

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
is_root = [False] + [True] * N
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        parent[v] = u
        queue.append(v)
for i in range(1, N+1):
    print(parent[i])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
t=[[]for _ in range(n)]
ne=(n-1)*n//2
ne_s=set()
e=[]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  e.append([a,b])
  if b not in ne_s:
    ne_s.add(b)
    ne-=b
  t[a].append(b)
d=[0]*n
Q=[ne]
di=1
while Q:
  P=[]
  for i in Q:
    for j in t[i]:
      d[j]=max(d[j],di)
      P.append(j)
  di+=1
  Q=P
ans=[0]*n
for a,b in e:
  if d[a]+1!=d[b]:continue
  ans[b]=a+1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from collections import deque
n,m = inm()
chi = [{} for i in range(n+1)]
par = [{} for i in range(n+1)]
for i in range(n-1+m):
    a,b = inm()
    chi[a][b] = 1
    par[b][a] = 1
dep = [0]*(n+1)
rpar = [0]*(n+1)
for i in range(1,n+1):
    if len(par[i])==0:
        root = i
        break
ddprint("chi")
ddprint(chi)
ddprint("par")
ddprint(par)
ddprint(root)
q = deque([root])
while len(q)>0:
    p = q.popleft()
    d = dep[p]
    for z in chi[p]:
        if dep[z]<d+1:
            dep[z] = d+1
            rpar[z] = p
            q.append(z)
for i in range(1,n+1):
    print(rpar[i])

Submission status: Time Limit Exceeded

Solution code:
#16:38
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      pre[y] = x
      now.append(y)
print('\n'.join(map(lambda x: str(x+1) ,pre)))

Submission status: Time Limit Exceeded

Solution code:
#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      pre[y] = x
      now.append(y)
print('\n'.join(map(lambda x: str(x+1) ,pre)))

Submission status: Time Limit Exceeded

Solution code:
#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[x] == y:
        continue
      pre[y] = x
      now.append(y)
print('\n'.join(map(lambda x: str(x+1) ,pre)))

Submission status: Time Limit Exceeded

Solution code:
#16:38
n,m = map(int,input().split())
raw = [set() for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].add(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [10**6 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[x] == y:
        continue
      pre[y] = x
      now.append(y)
for x in pre:
  if x != 10**6:
    print(x+1)
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [10**6 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[x] == y:
        continue
      pre[y] = x
      now.append(y)
for x in pre:
  if x != 10**6:
    print(x+1)
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
inf = 10**6
pre = [-1 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[x] == y:
        continue
      pre[y] = x
      now.append(y)
for x in pre:
  print(x+1)

Submission status: Time Limit Exceeded

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

G = [set() for i in range(N)]
count = [0]*N
for a, b in(AB):
    a -= 1
    b -= 1
    G[a].add(b)
    count[b] += 1
root = 0
for i in range(N):
    if count[i] == 0:
        root = i
        break
level = [-1]*N
parent = [0]*(N)

q = collections.deque()
q.append((root, 0))
while(q):
    x, l = q.popleft()
    for y in G[x]:
        if level[y] < level[x]+1:
            level[y] = l+1
            parent[y] = x+1
            q.append((y, l+1))


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

E = [[] for _ in range(N)]
root = [True] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    root[B-1] = False
root = root.index(True)

dist = [-1] * N
dist[root] = 0
parent = [-1] * N
q = deque([root])
while q:
    par = q.popleft()
    for e in E[par]:
        if dist[e] < dist[par] + 1:
            parent[e] = par
            dist[e] = dist[par] + 1
            q.append(e)

for ans in parent:
    print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
E = [[] for _ in range(N)]
root = [True] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    root[B-1] = False
root = root.index(True)

from collections import deque

dist = [-1] * N
dist[root] = 0
parent = [-1] * N
q = deque([root])
while q:
    par = q.pop()
    for e in E[par]:
        if dist[e] < dist[par] + 1:
            parent[e] = par
            dist[e] = dist[par] + 1
        q.append(e)

for ans in parent:
    print(ans + 1)

Submission status: Time Limit Exceeded

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

while q:
  p, cnt = q.popleft()
  if dist[p]>cnt:
    continue
  for e in dic[p]:
    if dist[e]<dist[p]+1:
      dist[e] = dist[p]+1
      q += [(e,dist[e])]
      par[e] = p
for i in range(1,N+1):
  print(par[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 = [set([]) for _ in range(N+1)]
e_to = [set([]) for _ in range(N+1)]
for _ in range(N + M - 1):
    a, b = map(int, input().split())
    e_from[a].add(b)
    e_to[b].add(a)


rank = [-1] * (N + 1)  # 親のノード番号
seen = set([])  # 既に確定したノード

# まず根を探す
for i in range(1, N+1):
    if len(e_to[i]) == 0:
        root = i
        break

# BFS
seen.add(root)
rank[root] = 0
node = deque([root])
while node:
    s = node.popleft()
    for t in e_from[s]:
        if len(e_to[t] - seen) == 0:
            rank[t] = s
            seen.add(t)
            node.append(t)

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
excess = []
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  for y in tree_go[x]:
    que.append((y,x))
print(*parent[1:],sep="\n")

Submission status: Time Limit Exceeded

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)
ans = [0]*N
cnt = []
while q:
    for i in range(len(q)):
        s = q.popleft()
        for x in cnt:
            if s in G[x]:
                ans[s] = x+1
        cnt.append(s)
        for t in G[s]:
            d[t] -= 1
            if d[t] == 0:
                q.append(t)
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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: Time Limit Exceeded

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)

r=[i for i in range(n) if not p[i]]

v=[-1]*n
def dfs(x):
    v[x]=0
    q=[x]
    while q:
        c=q.pop()
        for nb in g[c]:
            v[nb]=max(v[nb],v[c]+1)
            q.append(nb)
    return

dfs(r[0])
par=[0]*n
par[r[0]]=0


q=[r[0]]
while q:
    pr=q.pop()
    for ch in g[pr]:
        if v[ch]==v[pr]+1:
            q.append(ch)
            par[ch]=pr+1

for i in par:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	while Q:
		f = Q.popleft()
		inQ[f] = False
		for t, c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					Q.append(t)
					inQ[t] = True
					cnt[t] += 1
					front = Q.popleft()
					if d[front] > dist:
						Q.append(front)
					else:
						Q.appendleft(front)
				if cnt[t] > V:
					# negative cycle
					return None
	return d


def main():
	n, m, *L = map(int, open(0).read().split())
	con = [[] for _ in range(n)]
	g = []
	c = [True] * n
	for s, t in zip(*[iter(L)] * 2):
		con[s - 1] += [(t - 1, - 1)]
		c[t - 1] = False
	for i in range(n):
		if c[i]:
			root = i
			break
	dist = SPFA(con, root)
	ans = [0] * n
	for s, t in zip(*[iter(L)] * 2):
		if dist[t - 1] == dist[s - 1] - 1:
			ans[t - 1] = s
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	while Q:
		f = Q.popleft()
		inQ[f] = False
		for t, c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					Q.append(t)
					inQ[t] = True
					cnt[t] += 1
					front = Q.popleft()
					if d[front] > dist:
						Q.append(front)
					else:
						Q.appendleft(front)
				if cnt[t] > V:
					# negative cycle
					return None
	return d


def main():
	n, m, *L = map(int, open(0).read().split())
	con = [[] for _ in range(n)]
	g = []
	c = [True] * n
	for s, t in zip(*[iter(L)] * 2):
		con[s - 1] += [(t - 1, - 1)]
		c[t - 1] = False
	for i in range(n):
		if c[i]:
			root = i
			break
	dist = SPFA(con, root)
	ans = [0] * n
	for s, t in zip(*[iter(L)] * 2):
		if dist[t - 1] == dist[s - 1] - 1:
			ans[t - 1] = s
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[t-1]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
q=[root]
ans=[0]*n
while q:
	cur=q.pop(0)
	for nxt in con[cur]:
		ans[nxt]=cur+1
		q.append(nxt)
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[t-1]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
q=[(None,root)]
ans=[0]*n
while q:
	bef,cur=q.pop(0)
	for nxt in con[cur]:
		if nxt==bef:
			pass
		ans[nxt]=cur+1
		q.append((cur,nxt))
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[t-1]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
q=[(None,root)]
ans=[0]*n
while q:
	bef,cur=q.pop(0)
	for nxt in con[cur]:
		if nxt==bef:
			pass
		ans[nxt]=cur+1
		q.append((cur,nxt))
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

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

G = {k: [] for k in range(N+1)}
r = [True]*(N+1)
for _ in range(N+M-1):
    a, b = map(int, input().split())
    r[b] = False
    # 有向グラフ
    G[a].append(b)

for i in range(1, N+1):
    if r[i] is True:
        root = i


P = [-1]*(N+1)
P[root] = 0
dist = [-1]*(N+1)

que = [(root, 0, 0)]


while que:
    ci, pi, d = que.pop()
    if d > dist[ci]:
        P[ci] = pi
        dist[ci] = d

    for ni in G[ci]:
        if d+1 > dist[ni]:
            que.append((ni, ci, d+1))

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

Submission status: Time Limit Exceeded

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

G = {k: [] for k in range(N+1)}
r = [True]*(N+1)
for _ in range(N+M-1):
    a, b = map(int, input().split())
    r[b] = False
    # 有向グラフ
    G[a].append(b)

for i in range(1, N+1):
    if r[i] is True:
        root = i


P = [-1]*(N+1)
P[root] = 0
dist = [-1]*(N+1)

que = deque([(root, 0, 0)])


while que:
    ci, pi, d = que.popleft()
    if d > dist[ci]:
        P[ci] = pi
        dist[ci] = d

    for ni in G[ci]:
        que.append((ni, ci, d+1))

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

Submission status: Time Limit Exceeded

Solution code:
def dfs(n,e,fordfs):
    P = [-1]*n
    L = [0]*n
    que = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.pop()
        for ne in fordfs[now]:
            if P[ne] == -1:
                L[ne] = L[now]+1
                P[ne] = now + 1
                que.append(ne)
            elif L[ne]<L[now]+1:
                L[ne] = L[now]+1
                P[ne] = now + 1
                que.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = dfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    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: Time Limit Exceeded

Solution code:
def bfs(n,e,fordfs):
    P = [-1]*n
    L = [0]*n
    que = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if P[ne] == -1:
                L[ne] = L[now]+1
                P[ne] = now + 1
                que.append(ne)
            elif L[ne]<L[now]+1:
                L[ne] = L[now]+1
                P[ne] = now + 1
                que.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    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: Time Limit Exceeded

Solution code:
def bfs(n,e,fordfs):
    d = defaultdict(int)
    P = [-1]*n
    que = deque(); que2 = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if P[ne] == -1:
                que.append(ne)
                P[ne] = now + 1
            else:
                P[ne] = now + 1
                que2.append(ne)
    while que2:
        now = que2.popleft()
#        if d[now]:
#            continue
#        d[now] = True
        for ne in fordfs[now]:
            P[ne] = now + 1
            que2.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    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: Time Limit Exceeded

Solution code:
def bfs(n,e,fordfs):
    W = [-1]*n
    W[e] = 0
    P = [-1]*n
    que = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        nowW = W[now]
        for ne in fordfs[now]:
            if W[ne] == -1:
                W[ne] = nowW + 1
                que.append(ne)
                P[ne] = now + 1
            else:
                W[ne] = nowW + 1
                P[ne] = now + 1
                que.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    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: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int,input().split())
root = [1]*N
side = [[]for i in range(N)]

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

queue = deque([root.index(1)])
cost = [0]*N
oya = [0]*N
while queue:
    q = queue.popleft()
    for i in side[q]:
        if cost[i] <= cost[q]:
            cost[i] = cost[q]+1
            oya[i] = q+1
            queue.append(i)

for i in oya:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
v = [[] for _ in range(N)]
p = [True] * N
for _ in range(N + M - 1) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    p[B-1] = False
    
s = p.index(True)
dist = [0] * N
par = [-1] * N

q = deque([s])
while q :
    cur = q.popleft()
    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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dic = {}
npflag = [True] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

for i in range(N):

    print (p[i]+1)