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:
# -*- 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
      p[y] = x
      q.append(y)
      
print(*[i+1 for i in p],sep="\n")

Submission status: Wrong Answer

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])
c = 0
while q:
  c += 1
  x = q.popleft()
  for y in graph_to[x]:
    if d[y] < d[x] + 1:
      d[y] = d[x] + 1
      q.append(y)
  if c == 10**6:
    exit()
      
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: Wrong Answer

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)
    if d[y] != -1: continue
    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: Wrong Answer

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():
  global G
  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
    G[v]=[]
  return len(D)

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

Submission status: Wrong Answer

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

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)]
get_into = [0]*N
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    get_into[b-1] += 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]:
        get_into[nx] -= 1
        if get_into[nx]==1:
            parents[nx] = v
            Q.append(nx)

for p in parents:
    print(p+1)

Submission status: Wrong Answer

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

parents = [-1]*N
from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        if parents[nx]==v: continue
        parents[nx] = v
        Q.append(nx)

for p in parents:
    print(p+1)

Submission status: Wrong Answer

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)]
s = set()
root = 0
for a, b in AB:
    a -= 1
    b -= 1
    G[a].add(b)
    s.add(b)

for i in range(N):
    if i in s:
        continue
    else:
        root = i
        break

q = collections.deque()
q.append(root)
r = set([root])
parent = [-1]*N
parent[root] = 0
while(q):
    x = q.popleft()
    for y in G[x]:
        if (x, y) not in r:
            r.add((x, y))
            q.append(y)
        parent[y] = x+1

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

Submission status: Wrong Answer

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)]
s = set()
root = 0
for a, b in AB:
    a -= 1
    b -= 1
    G[a].add(b)
    s.add(b)

for i in range(N):
    if i in s:
        continue
    else:
        root = i
        break

q = collections.deque()
q.append(root)
r = set([root])
parent = [-1]*N
parent[root] = 0
while(q):
    x = q.popleft()
    for y in G[x]:
        if y not in r:
            r.add(y)
            q.append(y)
        parent[y] = x+1

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = [0]*n
c = [0]*n
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  s[a] += 2**b
  c[a] += 2**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,0,lambda a, b: a|b)
for i,ci in enumerate(c):
  S.update(i,ci)
  
p = 2**n-1
ans = [0]*n
root = deque()
root.append(-1)
l = [1]*n

while root:
  now = root.popleft()
  if now >= 0:
    S.update(now,0)
    l[now] -= 1
  child = p-S.seg[1]
  while True:
    k = child&(-child)
    nex = k.bit_length()-1
    ans[nex] = now+1
    if nex == -1:
      break
    root.append(nex)
    p -= 1<<nex
    child -= k
    if child == 0:
      break

  if now >= 0 and l[now] != 0:
    S.update(now,s[now])
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    fro=[[]for _ in range(N)]
    to=[[]for _ in range(N)]
    
    for _ in range(N+M-1):
        a,b=MI()
        a-=1
        b-=1
        fro[b].append(a)
        to[a].append(b)
        
    root=0
    for i in range(N):
        if len(fro[i])==0:
            root=i
            break
        
    P=[-1]*N
    
    
    import queue
    q=queue.Queue()
    q.put(root)
    
    while not q.empty():
        v=q.get()
        for nv in to[v]:
            if P[nv]==-1:
                q.put(nv)
            P[nv]=v
                
    for i in range(N):
        print(P[i]+1)
    
        

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    fro=[[]for _ in range(N)]
    to=[[]for _ in range(N)]
    dum=[]
    
    for _ in range(N+M-1):
        a,b=MI()
        a-=1
        b-=1
        fro[b].append(a)
        to[a].append(b)
        
    root=0
    for i in range(N):
        if len(fro[i])==0:
            root=i
            break
        
    P=[0]*N
    P[root]=-1
    
    
    import queue
    q=queue.Queue()
    q.put((root,-1))
    
    while not q.empty():
        v,p=q.get()
        for nv in to[v]:
            if nv!=p:
                if P[nv]==0:
                    q.put((nv,v))
                P[nv]=v
                
    for i in range(N):
        print(P[i]+1)
    
        

main()

Submission status: Wrong Answer

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

if 0 in s:
    ans = [-1]*n
    p = s.index(0)
    ans[p] = 0
    q = deque([])
    q.append(p)
    while q:
        now = q.popleft()
        for nex in e[now]:
            if ans[nex] == -1:
                ans[nex] = now+1
                q.append(nex)
    for i in ans:
        print(i)
    exit()

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

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


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

for i,s in enumerate(pps):
    if not s:
        r = i
        
def bfs(start):
    q = [start]
    seen = [None] * n
    seen[start] = 0
    d= 0
    while q:
        u = q.pop()
        for v in ns[u]:
            if seen[v] is None:
                d += 1
                seen[v] = d
                q.append(v)
    return seen

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

Submission status: Wrong Answer

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


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

for i,s in enumerate(pps):
    if not s:
        r = i
        
ps = [None] * n    
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
                ps[v] = u+1
            elif seen[v]<d+1:
                ps[v] = u+1
    return seen

ds = bfs(r)
ps[r] = 0
write("\n".join(map(str, ps)))

Submission status: Wrong Answer

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


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

for i,s in enumerate(pps):
    if not s:
        r = i
        
ps = [None] * n    
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
                ps[v] = u+1
            else:
                ps[v] = u+1
    return seen

ds = bfs(r)
ps[r] = 0
write("\n".join(map(str, ps)))

Submission status: Wrong Answer

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

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

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

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

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