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: Wrong Answer

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)]
redges = [[] for _ in range(N)]
for i in range(N-1+M):
  a, b = reads()
  edges[a-1].append(b-1)
  redges[b-1].append(a-1)

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

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

while len(que) != 0:
  x = que.popleft()
  for y in edges[x]:
    par[y] = x
    if not visited[y]:
      que.append(y)
      visited[y] = True

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

Submission status: Time Limit Exceeded

Solution code:
# another sol
import heapq

def main():
    n, m = map(int, input().split())
    G = [[] for i in range(n+1)]
    Edge = []
    is_root = [True]*(n+1)
    
    for _ in range(n+m-1):
        x, y = map(int, input().split())
        G[x].append(y)
        Edge.append((x, y))
        is_root[y] = False

    #determine root
    root = -1
    for i in range(1, n+1):
        if is_root[i] == True:
            root = i
            break

    que = [(0, root)]
    heapq.heapify(que)
    #dijkstra
    dis = [0]*(n+1)
    while que:
        cost, node = heapq.heappop(que)
        if dis[node] < cost:continue        
        for c in G[node]:
            if dis[c] > cost - 1:
                dis[c] = cost - 1
                heapq.heappush(que,(cost - 1, c))

    par = [0]*(n+1)

    for x, y in Edge:
        if dis[y] + 1 == dis[x]:
            par[y] = x

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

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
## Atcoder problem solving


# type tree
import heapq


def main():
    n, m = map(int, input().split())
    G = [[] for i in range(n+1)]
    Edge = []
    is_root = [True]*(n+1)
    
    for _ in range(n+m-1):
        x, y = map(int, input().split())
        G[x].append(y)
        Edge.append((x, y))
        is_root[y] = False

    #determine root
    root = -1
    for i in range(1, n+1):
        if is_root[i] == True:
            root = i
            break

    que = [(0, root)]
    heapq.heapify(que)

    #dijkstra
    dis = [10**10]*(n+1)
    dis[root] = 0
    while que:

        cost, node = heapq.heappop(que)
        for c in G[node]:
            if dis[c] > cost - 1:
                dis[c] = cost - 1
                heapq.heappush(que,(cost - 1, c))


    par = [0]*(n+1)

    for x, y in Edge:
        if dis[y] + 1 == dis[x]:
            par[y] = x

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

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[] for i in range(n)]
edges_r = [[] for i in range(n)]
for i in range(n+m-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges_r[b].append(a)
s = 0
for i,e in enumerate(edges_r):
    if len(e) == 0:
        s = i
        break

INF = 1 << 60
ks = [-1] * n
parents = [-1] * n
q = deque([s])
ks[s] = 0
# 同じ深さのもの同士をつなぐのはありえないので
# 根の部分から徐々に掘り下げながら、真の親を探す
while len(q) > 0:
    u = q.popleft()
    for v in edges[u]:
        if ks[u] >= ks[v]:
            ks[v] = ks[u] + 1
            parents[v] = u
            q.appendleft(v)

for p in parents:
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
edges = [[] for i in range(n)]
edges_r = [[] for i in range(n)]
for i in range(n+m-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges_r[b].append(a)
ns = [(len(e),i) for i, e in enumerate(edges_r)]
ns.sort()
s = ns[0][1]

INF = 1 << 60
ks = [-1] * n
parents = [-1] * n
q = deque([s])
ks[s] = 0
# 同じ深さのもの同士をつなぐのはありえないので
# 根の部分から徐々に掘り下げながら、真の親を探す
while len(q) > 0:
    u = q.popleft()
    for v in edges[u]:
        if ks[u] >= ks[v]:
            ks[v] = ks[u] + 1
            parents[v] = u
            q.appendleft(v)

for p in parents:
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(N, M, G, root):
    P = [-1] * N
    D = [-1] * N
    q = deque()
    q.append((root, 0, -1))
    while q:
        v, d, p = q.popleft()
        if D[v] < d:
            D[v] = d
            P[v] = p
        for to in G[v]:
            q.append((to, d + 1, v))
    for p in P:
        print(p + 1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    I = [0] * N
    for _ in range(N - 1 + M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        I[b] += 1
    main(N, M, G, I.index(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

Submission status: Time Limit Exceeded

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

# import numpy as np

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

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


# ===CODE===


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

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

    root_idx = root.index(True)

    que = collections.deque([root_idx])
    while que:
        q = que.popleft()

        for ei in e[q]:
            ans[ei] = q
            que.append(ei)

    for ansi in ans:
        print(ansi + 1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

v_root = in_degree.index(0)

ans = [0] * n
queue = deque([v_root])
while queue:
    v = queue.popleft()
    for v_next in graph[v]:
        ans[v_next] = v + 1
        queue.append(v_next)

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

Submission status: Time Limit Exceeded

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

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

v_root = in_degree.index(0)

ans = [0] * n
queue = deque([v_root])
while queue:
    v = queue.popleft()
    for v_next in graph[v]:
        ans[v_next] = v + 1
        queue.append(v_next)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from heapq import *
import sys
S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
X=[0]*N
for i in range(N+M-1):
  a,b=map(int,S[i+1].split())
  X[b-1]=1
  G[a-1].append(b-1)
R=X.index(0)
Z=[0]*N
INF=10**12
def ijk(s):
  for i in range(len(G)):
    Z[i]=INF
  Z[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if Z[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if Z[e]>Z[v]-1:
        Z[e]=Z[v]-1
        heappush(Q,(Z[e],e))

ijk(R)
A=[0]*N
D=[0]*N
def ijk2(s):
  for i in range(len(G)):
    D[i]=INF
  D[s]=0
  Q=[]
  heapify(Q)
  heappush(Q,(0,s))
  p,v,e=0,0,0
  while len(Q):
    p=heappop(Q)
    v=p[1]
    if D[v]<p[0]:
      continue
    for i in range(len(G[v])):
      e=G[v][i]
      if D[e]>D[v]-1:
        D[e]=D[v]-1
        heappush(Q,(D[e],e))
      if D[e]==Z[e]:
        A[e]=v+1

ijk2(R)
print(*A,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import *
import sys
S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
X=[0]*N
for i in range(N+M-1):
  a,b=map(int,S[i+1].split())
  X[b-1]=1
  G[a-1].append(b-1)
R=X.index(0)
D=[0]*N
Q=deque([R])
def dfs1(x):
  v=0
  for i in range(len(Q)):
    v=Q.popleft()
    for j in range(len(G[v])):
      D[G[v][j]]=x+1
      Q.append(G[v][j])
  return len(Q)==0

A=[0]*N
def dfs2(x):
  v=0
  for i in range(len(Q)):
    v=Q.popleft()
    for j in range(len(G[v])):
      if D[G[v][j]]==x+1:
        Q.append(G[v][j])
        A[G[v][j]]=v+1
  return len(Q)==0

for i in range(N+M):
  if dfs1(i):
    break
Q=deque([R])
for i in range(N+M):
  if dfs2(i):
    print(*A,sep='\n')
    break

Submission status: Time Limit Exceeded

Solution code:
from collections import *
N,M=map(int,input().split())
G=[[] for i in range(N)]
a,b=0,0
X=[0]*N
for i in range(N+M-1):
  a,b=map(int,input().split())
  X[b-1]=1
  G[a-1].append(b-1)
R=X.index(0)
D=[0]*N
Q=deque([R])
def dfs1(x):
  v=0
  for i in range(len(Q)):
    v=Q.popleft()
    for j in range(len(G[v])):
      D[G[v][j]]=x+1
      Q.append(G[v][j])
  return len(Q)==0

A=[0]*N
def dfs2(x):
  v=0
  for i in range(len(Q)):
    v=Q.popleft()
    for j in range(len(G[v])):
      if D[G[v][j]]==x+1:
        Q.append(G[v][j])
        A[G[v][j]]=v+1
  return len(Q)==0

for i in range(N+M):
  if dfs1(i):
    break
Q=deque([R])
for i in range(N+M):
  if dfs2(i):
    print(*A,sep='\n')
    break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush,heapify,heappop
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

v = 0
while co[v]:
    v = co[v][0]

def dijkstra(s):
    prev = [-1] * n  # 経路復元
    INF = -(1 << 32)
    d = [INF] * n  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] > -p[0]:
            continue
        for e in es[v]:
            if d[e] < d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (-d[e], e)) 
                prev[e] = v
    return d, prev
_, parent = dijkstra(v)


for i in parent:
    print(i+1)

Submission status: Time Limit Exceeded

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

v = 0
while co[v]:
    v = co[v][0]

parent = [-1] * n
parent[v] = 0

q = deque([v])

while q:
    v = q.popleft()
    for e in es[v]:
        parent[e] = v + 1
        q.append(e)

for i in parent:
    print(i)

Submission status: Time Limit Exceeded

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

v = 0
while co[v]:
    v = co[v][0]

parent = [-1] * n
parent[v] = 0

q = deque([v])

while q:
    v = q.popleft()
    for e in es[v]:
        f = 1
        for p in co[e]:
            if parent[p] == -1:
                f = 0
                break
        if f:
            parent[e] = v + 1
            q.append(e)

for i in parent:
    print(i)

Submission status: Time Limit Exceeded

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#############
# Main Code #
#############

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

for i in range(N+M-1):
  a,b = IL()
  graph_to[a-1].add(b-1)
  graph_from[b-1].add(a-1)
for i in range(N):
  if not graph_from[i]:
    root = i
    
d = [-1 for i in range(N)]
p = [-1 for i in range(N)]
d[root] = 0
q = deque([root])
while q:
  x = q.popleft()
  d[x] = d[p[x]] + 1
  for y in graph_to[x]:
    if d[y] < d[x] + 1:
      d[y] = d[x] + 1
      p[y] = x
      q.append(y)
      
print(*[i+1 for i in p],sep="\n")

Submission status: Time Limit Exceeded

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#############
# Main Code #
#############

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

for i in range(N+M-1):
  a,b = IL()
  graph_to[a-1].add(b-1)
  graph_from[b-1].add(a-1)
for i in range(N):
  if not graph_from[i]:
    root = i
    
d = [-1 for i in range(N)]
p = [-1 for i in range(N)]
d[root] = 0
q = deque([root])
while q:
  x = q.popleft()
  for y in graph_to[x]:
    if d[y] < d[x] + 1:
      d[y] = d[x] + 1
      p[y] = x
      q.append(y)
      
print(*[i+1 for i in p],sep="\n")

Submission status: Time Limit Exceeded

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#############
# Main Code #
#############

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

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

def depth(x):
  if p[x] == -1:
    return 0
  if d[x] == d[p[x]] + 1:
    return d[x]
  else:
    return d[x]
    d[p[x]] = depth(p[x])
    return d[p[x]] + 1
    
d = [-1 for i in range(N)]
p = [-1 for i in range(N)]
d[root] = 0
q = deque([root])
while q:
  x = q.popleft()
  for y in graph_to[x]:
    if depth(y) < depth(x) + 1:
      d[y] = d[x] + 1
      p[y] = x
      q.append(y)
      
print(*[i+1 for i in p],sep="\n")