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:
# -*- 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:
    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
      q.append(y)
      
ans_graph_from = [0 for i in range(N)]
for x in range(N):
  for y in graph_from[x]:
    if d[x] == d[y]+1:
      ans_graph_from[x] = y+1
print(*ans_graph_from,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 depth(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
      q.append(y)
      
ans_graph_from = [0 for i in range(N)]
for x in range(N):
  for y in graph_from[x]:
    if d[x] == d[y]+1:
      ans_graph_from[x] = y+1
print(*ans_graph_from,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)]
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
      q.append(y)
      
ans_graph_from = [0 for i in range(N)]
for x in range(N):
  for y in graph_from[x]:
    if d[x] == d[y]+1:
      ans_graph_from[x] = y+1
print(*ans_graph_from,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)]
d[root] = 0
prev = None
while prev != d:
  prev = d[:]
  q = deque([root])
  while q:
    x = q.pop()
    for y in graph_to[x]:
      if d[y] < d[x] + 1:
        d[y] = d[x] + 1
        q.append(y)
      
ans_graph_from = [0 for i in range(N)]
for x in range(N):
  for y in graph_from[x]:
    if d[x] == d[y]+1:
      ans_graph_from[x] = y+1
print(*ans_graph_from,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)]
d[root] = 0
q = deque([root])
while q:
  x = q.pop()
  for y in graph_to[x]:
    if d[y] < d[x] + 1:
      d[y] = d[x] + 1
      q.append(y)
      
ans_graph_from = [0 for i in range(N)]
for x in range(N):
  for y in graph_from[x]:
    if d[x] == d[y]+1:
      ans_graph_from[x] = y+1
print(*ans_graph_from,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import *
N,M=map(int,input().split())
a,b=0,0
G=[[] for i in range(N)]
R=list(range(N))
for i in range(N+M-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  G[a].append(b)
  R[b]=-1
R=max(R)
D=deque()
P=[0]*N
S=set()
def qao(x):
  D.append(x)
  S.add(x)
  return True

def bfs():
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(len(G[v])):
      if qao(G[v][j]):
        P[G[v][j]]=v+1
  return len(D)

qao(R)
while bfs():
  pass
print(*P,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        parents[nx] = v
        Q.append(nx)

for p in parents:
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ALL = set([])
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.add(b)
#print(Graph,gyaku)
for i in range(N):
  if i not in ALL:
    root = i
    break

used = [0 for _ in range(N)]
used[root] +=1
ans = [0 for _ in range(N)]
Q = [root]
while Q:
  v = Q.pop()
  #print(v,Q,used[v])
  if used[v] > 1:
    used[v] -=1
    continue
  used[v] -=1
  #print(v,Q)
  for w in Graph[v]:
    ans[w] = v+1
    used[w] += 1
    Q.append(w)
for x in ans:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ALL = set([])
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.add(b)
#print(Graph,gyaku)
for i in range(N):
  if i not in ALL:
    root = i
    break

ans = [0 for _ in range(N)]
Q = [root]
while Q:
  v = Q.pop()
  for w in Graph[v]:
    ans[w] = v+1
    Q.append(w)
for x in ans:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
T = {}
for _ in range(N+M-1):
    a,b = map(int,input().split())
    if a not in T:
        T[a] = [[],[]]
    T[a][1].append(b)
    if b not in T:
        T[b] = [[],[]]
    T[b][0].append(a)
for i in range(1,N+1):
    if len(T[i][0])==0:
        rt = i
        break
dist = [-1 for _ in range(N+1)]
que = deque([(rt,0)])
dist[rt] = 0
while que:
    a,d = que.popleft()
    for x in T[a][1]:
        dist[x]=d+1
        que.append((x,d+1))
pa = {i:0 for i in range(1,N+1)}
for i in range(1,N+1):
    if i!=rt:
        for x in T[i][0]:
            if dist[x]==dist[i]-1:
                pa[i] = x
                break
for i in range(1,N+1):
    print(pa[i])

Submission status: Time Limit Exceeded

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([])
ans = [0 for _ in range(N)]
Q = [root]
while Q:
  v = Q.pop()
  for w in Graph[v]:
    ans[w] = v+1
    Q.append(w)
for x in ans:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int, input().split())
E = [[] for _ in range(N)]
memo = [0]*N
for _ in range(N+M-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    memo[b-1] = 1

root = memo.index(0)
rnk = [0]*N
par = [-1]*N

h = [-root]
while h:
    temp = heapq.heappop(h)
    temp *= -1
    u = temp%N
    r = temp//N
    for v in E[u]:
        if rnk[v] > r+1:
            continue
        rnk[v] = r+1
        par[v] = u
        heapq.heappush(h, -(r+1)*N-v)

for p in par:
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
T = {}
Tr = {}
for _ in range(N+M-1):
    a,b = map(int,input().split())
    if a not in T:
        T[a] = [0,[]]
    T[a][1].append(b)
    if b not in T:
        T[b] = [0,[]]
    T[b][0] += 1
    if b not in Tr:
        Tr[b] = []
    Tr[b].append(a)
for i in range(1,N+1):
    if T[i][0]==0:
        rt = i
        break
dist = [-1 for _ in range(N+1)]
que = deque([(rt,0)])
dist[rt] = 0
while que:
    a,d = que.popleft()
    for x in T[a][1]:
        dist[x]=d+1
        que.append((x,d+1))
pa = {i:0 for i in range(1,N+1)}
for i in range(1,N+1):
    if i!=rt:
        for x in Tr[i]:
            if dist[x]==dist[i]-1:
                pa[i] = x
                break
for i in range(1,N+1):
    print(pa[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M = map(int, input().split())
E = [[] for _ in range(N)]
memo = [0]*N
for _ in range(N+M-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    memo[b-1] = 1

root = memo.index(0)
rnk = [0]*N
par = [-1]*N

h = [root]
while h:
    temp = heapq.heappop(h)
    u = temp%N
    r = temp//N
    for v in E[u]:
        if rnk[v] > r+1:
            continue
        rnk[v] = r+1
        par[v] = u
        heapq.heappush(h, (r+1)*N+v)

for p in par:
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  ki[a].append(b)
root=root_kouho.pop()
p=[-1]*n
p[root]=0
todo=[[root,-1,0]]
ans=[-1]*n
ans[root]=0
seen=[0]*n
#todo=[[root,-1]]
while todo:
  t,p,d=todo.pop()
  for li in ki[t]:
    if li!=p:
      if seen[li]==-1 or seen[li]<d+1:
        ans[li]=t+1
        seen[li]=d+1
        todo.append([li,t,d+1])
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
root_kouho=set(list(range(n)))
ki=[[] for _ in range(n)]
for i in range(n-1+m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  root_kouho.discard(b)
  ki[a].append(b)
root=root_kouho.pop()
from collections import deque
p=[-1]*n
p[root]=0
todo=deque([[root,-1]])
ans=[-1]*n
ans[root]=0
#todo=[[root,-1]]
while todo:
  t,p=todo.popleft()
  for li in ki[t]:
    if li!=p:
      ans[li]=t+1
      todo.append([li,t])
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
s = [set() for i in range(n)]
c = [set() for i in range(n)]
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  s[a].add(b)
  c[a].add(b)
  
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc
                
    def update(self, k, r):
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k*2], self.seg[k*2+1])

S = segment_(n,set(),lambda a, b: a|b)
for i,ci in enumerate(c):
  S.update(i,ci)
  
p = set([int(i) for i in range(n)])
ans = [0]*n
root = deque()
root.append(-1)
cnt = 0

while root:
  if cnt == n:
    break
  now = root.popleft()
  if now >= 0:
    S.update(now,set())
  child = p-S.seg[1]
  for nex in child:
    cnt += 1
    ans[nex] = now+1
    root.append(nex)
    p.remove(nex)
print(*ans,sep='\n')