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:

class Graph:
    def __init__(self, n_vertices, edges, directed=True):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            if self.directed:
                for u,v in self.edges:
                    adj[u].append(v)
            else:
                for u,v in self.edges:
                    adj[u].append(v)
                    adj[v].append(u)
            self._adj = adj
            return adj

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(N, edges):
    adj = Graph(N, edges, directed=True).adj
    parent = [-1]*N
    
    # find root
    candidates = [True]*N
    for a,b in edges:
        candidates[b] = False

    root = next(v for v,f in enumerate(candidates) if f)
    visited = [False]*N
    q = [root]
    while q:
        nq = []
        for v in q:
            for u in adj[v]:
                if parent[u] != v:
                    parent[u] = v
                    if not visited[u]:
                        nq.append(u)
                        visited[u] = True
        q = nq
    return (p+1 for p in parent)




if __name__ == '__main__':
    N,M = map(int,readline().split())
    m = map(lambda x: int(x)-1, read().split())
    edges = list(zip(m,m))
    print(*solve(N,edges), sep='\n')

Submission status: Wrong Answer

Solution code:

class Graph:
    def __init__(self, n_vertices, edges, directed=True):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            if self.directed:
                for u,v in self.edges:
                    adj[u].append(v)
            else:
                for u,v in self.edges:
                    adj[u].append(v)
                    adj[v].append(u)
            self._adj = adj
            return adj

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(N, edges):
    adj = Graph(N, edges, directed=True).adj
    parent = [-1]*N
    
    # find root
    candidates = [True]*N
    for a,b in edges:
        candidates[b] = False

    root = next(v for v,f in enumerate(candidates) if f)

    q = [root]
    while q:
        nq = []
        for v in q:
            for u in adj[v]:
                if parent[u] != v:
                    parent[u] = v
                    nq.append(u)
        q = nq
    return (p+1 for p in parent)




if __name__ == '__main__':
    N,M = map(int,readline().split())
    m = map(lambda x: int(x)-1, read().split())
    edges = list(zip(m,m))
    print(*solve(N,edges), sep='\n')

Submission status: Wrong Answer

Solution code:

class Graph:
    def __init__(self, n_vertices, edges, directed=True):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            if self.directed:
                for u,v in self.edges:
                    adj[u].append(v)
            else:
                for u,v in self.edges:
                    adj[u].append(v)
                    adj[v].append(u)
            self._adj = adj
            return adj

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(N, edges):
    adj = Graph(N, edges, directed=True).adj
    parent = [-1]*N
    
    # find root
    candidates = [True]*N
    for a,b in edges:
        candidates[b] = False

    root = next(v for v,f in enumerate(candidates) if f)

    stack = [root]
    while stack:
        v = stack.pop()
        for u in adj[v]:
            if parent[u] != v:
                parent[u] = v
                stack.append(u)

    return (p+1 for p in parent)




if __name__ == '__main__':
    N,M = map(int,readline().split())
    m = map(lambda x: int(x)-1, read().split())
    edges = list(zip(m,m))
    print(*solve(N,edges), sep='\n')

Submission status: Wrong Answer

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


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    print(0)
    print(1)
    print(1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    print(0)
    print(1)
    print(2)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n,m=LI()
G=[[]for _ in range(n)]
cnt=[0]*n
for _ in range(n-1+m):
    a,b=LI()
    G[a-1]+=[b-1]
    cnt[b -1]+=1

r=cnt.index(0)
q=deque([r])
ans=[0]*n
while q:
    u=q.popleft()
    for v in G[u]:
        if not ans[v]:
            q+=[v]
        ans[v]=u+1


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n,m=LI()
G=[[]for _ in range(n)]
RG=[[]for _ in range(n)]
for _ in range(n-1+m):
    a,b=LI()
    G[a-1]+=[b-1]
    RG[b - 1] += [a - 1]

now=0
while RG[now]:
    now=RG[now][0]

r=now
q=deque([r])
ans=[0]*n
while q:
    u=q.popleft()
    for v in G[u]:
        if not ans[v]:
            q+=[v]
        ans[v]=u+1


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n,m=LI()
G=[[]for _ in range(n)]
RG=[[]for _ in range(n)]
for _ in range(n-1+m):
    a,b=LI()
    G[a-1]+=[b-1]
    RG[b - 1] += [a - 1]

now=0
while RG[now]:
    now=RG[now][0]

r=now
D=[0]*n
q=deque([r])
ans=[0]*n
while q:
    u=q.popleft()
    for v in G[u]:
        ans[v]=u+1
        if D[v]:
            continue
        D[v]=1
        q+=[v]

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

Submission status: Wrong Answer

Solution code:
# WA
print(0)
print(1)
print(1)

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, M, I):
    ans = [i[0] + 1 if i else 0 for i in I]
    for a in ans:
        print(a)

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

Submission status: Wrong Answer

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

def main():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    par_judge = [[] for _ in range(n)]
    for i in range(n+m-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        par_judge[b-1].append(a-1)
    
    for i in range(n):
        if par_judge[i] == []:
            root = i
            break
    
    par = [0]*n
    already = [False]*n
    
    dist = [0]*n
    not_yet = deque([root])
    already[root] = True
    while not_yet:
        key = not_yet.popleft()
        for v in tree[key]:
            if dist[v] > dist[key] + 1:
                continue
            par[v] = key+1
            dist[v] = dist[key]+1
            if already[v]:
                continue
            already[v] = True
            not_yet.append(v)
    
    for p in par:
        print(p)
 
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    par_judge = [[] for _ in range(n)]
    for i in range(n+m-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        par_judge[b-1].append(a-1)
    
    for i in range(n):
        if par_judge[i] == []:
            root = i
            break
    
    par = [0]*n
    already = [False]*n
    
    dist = [0]*n
    not_yet = deque([root])
    already[root] = True
    while not_yet:
        key = not_yet.popleft()
        for v in tree[key]:
            if dist[v] >= dist[key] + 1:
                continue
            par[v] = key+1
            dist[v] = dist[key]+1
            if already[v]:
                continue
            already[v] = True
            not_yet.append(v)
    
    for p in par:
        print(p)
 
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    par_judge = [[] for _ in range(n)]
    already = dict()
    for i in range(n+m-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        par_judge[b-1].append(a-1)
        already[(a-1, b-1)] = False
    
    for i in range(n):
        if par_judge[i] == []:
            root = i
            break
    
    par = [0]*n
    already2 = [False]*n
    
    dist = [0]*n
    not_yet = deque([root])
    already2[root] = True
    while not_yet:
        key = not_yet.popleft()
        
        for v in tree[key]:
            if already[(key, v)]:
                continue
            already[(key, v)] = True
            if dist[v] >= dist[key] + 1:
                continue
            par[v] = key+1
            dist[v] = dist[key]+1
            if already2[v]:
                continue
            already2[v] = True
            not_yet.append(v)
    
    for p in par:
        print(p)
 
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    par_judge = [[] for _ in range(n)]
    already = dict()
    for i in range(n+m-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        par_judge[b-1].append(a-1)
        already[(a-1, b-1)] = False
    
    for i in range(n):
        if par_judge[i] == []:
            root = i
            break
    
    par = [0]*n
    
    dist = [0]*n
    not_yet = deque([root])
    while not_yet:
        key = not_yet.popleft()
        
        for v in tree[key]:
            if already[(key, v)]:
                continue
            already[(key, v)] = True
            if dist[v] >= dist[key] + 1:
                continue
            par[v] = key+1
            dist[v] = dist[key]+1
            not_yet.append(v)
    
    for p in par:
        print(p)
 
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)]
check = [False 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
        if check[n_pos]:
            continue
        check[n_pos] = True
        queue.append(n_pos)
        queue.append(pos)
        
for pos in ans:
    print(pos)

Submission status: Wrong Answer

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)]
check = [False for _ in range(n)]
queue.append(rood)
queue.append(0)
while queue:
    pos = queue.popleft()
    b_pos = queue.popleft()
    check[pos] = True
    for n_pos in edges[pos]:
        ans[n_pos] = pos + 1
        if check[n_pos]:
            continue
        queue.append(n_pos)
        queue.append(pos)
        
for pos in ans:
    print(pos)

Submission status: Wrong Answer

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)]
    not_visited = [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])
    not_visited[root_idx] = False

    while que:
        q = que.popleft()

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

    for ansi in ans:
        print(ansi + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)]
    not_visited = [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])
    not_visited[root_idx] = True
    
    while que:
        q = que.popleft()

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

    for ansi in ans:
        print(ansi + 1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]:
        if parent[e] == -1:
            q.append(e)
        parent[e] = v + 1

for i in parent:
    print(i)

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 #
#############
def topological_sort(graph_to, graph_from):
  graph_from_cnt = [len(graph_from[i]) for i in range(N)]
  dic = DD(int)
  q = deque([i for i in range(N) if not graph_from_cnt])
  while q:
    x = q.popleft()
    dic[x] = len(dic)
    for y in graph_to[x]:
      graph_from_cnt[y] -= 1
      if not graph_from_cnt[y]:
        q.append(y)
  return dic


N,M = IL()
graph_to = [set() for i in range(N)]
graph_from = [set() for i in range(N)]
graph_from_cnt = [0 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)

dic = topological_sort(graph_to, graph_from)
  
ans = []
for y in range(N):
  d = -1
  p = 0
  for x in graph_from[y]:
    if dic[x] > d:
      d = dic[x]
      p = x+1
  ans.append(p)

print(*ans,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
f = [0 for i in range(N)]
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()
  if f[x]: continue
  f[x] = 1
  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")