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 -*-

import queue

n, m = map(int, input().split())
p = {i+1:set() for i in range(n)}

for i in range(n-1+m):
    a, b = map(int, input().split())
    p[b].add(a)

for c, ps in p.items():

    if len(ps) == 0:
        ps.add(0)
        continue
    elif len(ps) == 1:
        continue

    tp = set(ps)
    for parent in tp:
        ps.remove(parent)

        q = queue.Queue()
        q.put(c)
        visited = set()
        isExist = False
        while not q.empty():
            vq = q.get()
            visited.add(vq)
            if vq == parent:
                isExist = True
                break
            elif vq == 0:
                break
            for ttp in p[vq]:
                if not ttp in visited:
                    q.put(ttp)

        if not isExist:
            ps.clear()
            ps.add(parent)
            break

for i in range(n):
    print(list(p[i+1])[0])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

result = [-2] * N
edge_from = [[] for _ in range(N)]
edge_to = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    edge_from[B-1].append(A-1)
    edge_to[A-1].append(B-1)

parent = []
for i in range(N):
    if len(edge_to[i]) > 0 and len(edge_from[i]) == 0:
        parent.append(i)
        result[i] = -1

while True:
    next_ = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if len(edge_from[child]) == 0:
                result[child] = p
                next_.append(child)
    if not any(next_):
        break
    parent = next_.copy()

for x in result:
    print(x + 1)

Submission status: Wrong Answer

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

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1
used2 = used
#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    global used
    global res
    for e in down[z]:
        if used[e]==0 and g(e):
            used2[e]=1
            res[e]=z+1
            tank2.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
while c != n:
    tank = tank2
    tank2 = deque([])
    used = used2
    while len(tank)!=0:
        f(tank.popleft())
    c += len(tank2)
    
for i in range(n):
    print(res[i])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1

#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            used[e]=1
            res[e]=z+1
            f(e)
#f(root)
for i in range(n):
    print(res[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n + m - 1)]

seta = set()
setall = set(i for i in range(1, n + 1))
way = {}
for i in range(n + m - 1):
    seta.add(ab[i][1])
    if ab[i][0] in way:
        way[ab[i][0]].append(ab[i][1])
    else:
        way[ab[i][0]] = [ab[i][1]]
top = (setall - seta).pop()
cld = {i:top for i in way[top]}
nexta = way[top]
nowp = top
finished = set([top])
while len(nexta) != 0:
    nowp = nexta.pop(0)
    if nowp in way:
        finished.add(nowp)
        for i in way[nowp]:
            cld[i] = nowp
            if i not in finished:
                nexta.append(i)
                finished.add(i)
ans = [0] * (n + 1)
for i in cld:
    ans[i] = cld[i]
for i in range(1, n + 1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n + m - 1)]

seta = set()
setall = set(i for i in range(1, n + 1))
way = {}
for i in range(n + m - 1):
    seta.add(ab[i][1])
    if ab[i][0] in way:
        way[ab[i][0]].append(ab[i][1])
    else:
        way[ab[i][0]] = [ab[i][1]]
top = (setall - seta).pop()
cld = {i:top for i in way[top]}
nexta = way[top]
nowp = top
finished = set(nexta)
while len(nexta) != 0:
    nowp = nexta.pop(0)
    if nowp in way:
        finished.add(nowp)
        for i in way[nowp]:
            cld[i] = nowp
            if i not in finished:
                nexta.append(i)
                finished.add(i)
ans = [0] * (n + 1)
for i in cld:
    ans[i] = cld[i]
for i in range(1, n + 1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

n_in = [0] * n
graph = [[] for _ in range(n)]
for i in range(n+m-1):
    A, B = map(int, input().split())
    n_in[B-1] += 1
    graph[A-1].append(B-1)

root = 0
for i in range(n):
    if n_in[i] == 0:
        root = i
        break

route = []
q = deque([root])
count = 0
while q:
    node = q.popleft()
    route.append(node)
    for next_v in graph[node]:
        n_in[next_v] -= 1
        if n_in[next_v] == 0:
            q.append(next_v)

parent = [0] * n
for i, v in enumerate(route):
    if i == 0:
        parent[v] = (0, v)
    else:
        parent[v] = (route[i-1]+1, v)

parent.sort(key=lambda x: x[1])
for i in range(n):
    print(parent[i][0])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
in_counts = [0] * n
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    in_counts[b] += 1

root = 0
for v, ic in enumerate(in_counts):
    if ic == 0:
        root = v
        break

parents = [-1] * n
q = deque([(root, -1)])

while q:
    v, p = q.popleft()
    in_counts[v] -= 1
    if in_counts[v] == 0:
        parents[v] = p
        q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in parents))

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] == 0:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    # else:
    #     ans[tar:tar+1] = tmp[i][2][0:1]
    #     dic[tar] = -1
    i += 1

check = i
ch = 0
ans2 = [0 for _ in range(N+1)]
while ch <= 2 or ans2 != ans:
#    print(ans[1:])
    ans2 = ans
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = -1
            if dic[tar2] <= 0:
                if length < abs(dic[tar2]):
                    length = abs(dic[tar2]) + 1
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1
    if max(dic.values()) <= 1:
        ch += 1
#print(dic)
for a in ans[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

par = [[] for i in range(n)]
op = [[]for i in range(n)]
for i in range(n+m-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    par[y].append(x)
    op[x].append(y)

res = [-1]*n
x = -1


for i in range(n):
    if len(par[i])==0:
        res[i] = 0
        x = i
        print(1)
        exit()
        break


used = [0]*n
used[x]=1
def g(y):
    for pe in par[y]:
        if used[pe]==0:
            return False
    return True
    
#xの下のusedとresを埋める
def f(z):
    for e in op[z]:
        if used[e]==0 and g(e):
            used[e]=1
            res[e]=z+1
            f(e)
f(x)
for i in range(n):
    print(res[i])

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] <= 1:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    else:
        ans[tar:tar+1] = tmp[i][2][0:1]
        dic[tar] = -1
    i += 1

check = i
ch = 0
ans2 = [0 for _ in range(N+1)]
while ch <= 2 or ans2 != ans:
#    print(ans[1:])
    ans2 = ans
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = 0
            if dic[tar2] <= 0:
                if length < abs(dic[tar2]):
                    length = abs(dic[tar2]) + 1
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1
    if max(dic.values()) <= 1:
        ch += 1

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

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] <= 1:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    else:
        ans[tar:tar+1] = tmp[i][2][0:1]
        dic[tar] = -1
    i += 1

check = i
ch = 0
ans2 = [0 for _ in range(N+1)]
while ch <= 2 or ans2 != ans:
    ans2 = ans
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = 0
            if dic[tar2] <= 0:
                if length < abs(dic[tar2]):
                    length = abs(dic[tar2])
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1
    if max(dic.values()) <= 1:
        ch += 1

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

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] <= 1:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    else:
        ans[tar:tar+1] = tmp[i][2][0:1]
        dic[tar] = -1
    i += 1

check = i
ch = 0
ans2 = [0 for _ in range(N+1)]
while ch == 0 or ans2 != ans:
    ans2 = ans
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = 0
            if dic[tar2] <= 0:
                if length < abs(dic[tar2]):
                    length = abs(dic[tar2])
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1
    if max(dic.values()) <= 1:
        ch += 1

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

Submission status: Wrong Answer

Solution code:
def data_input():
    a,b = input().split(' ')
    return (int(a),int(b))
def data_input2(n,m):
    length = n + m - 1
    res = []
    for _ in range(length):
        a,b = input().split(' ')
        res.append((int(a),int(b)))
    return res
def answer():
    n,m = data_input()
    trees = data_input2(n,m)
    n += 1
    ins = [0 for _ in range(n)]
    out = [[] for _ in range(n)]
    res = [0 for _ in range(n)]
    for start,end in trees:
        ins[end] += 1
        out[start] += [end]
    stack = [i for i,n in enumerate(ins) if n > 2]
    while stack:
        target = stack.pop()
        for start,end in trees:
            if end == target:
                trees.remove((start,end))
                break
    for start,end in trees:
        res[end] = start
    return res[1:]
def output():
    res = answer()
    print(res)
output()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

N, M = map(int, input().split())
l = [[] for i in range(N+1)]
findroot = [0 for i in range(N+1)]
for i in range(N+M-1):
    A, B = map(int, input().split())
    findroot[B] = 1
    l[A].append(B)
for i in range(1, N+1):
    if findroot[i] == 0:
        first = i
depthlist = [0 for i in range(N+1)]
pathlist = [[] for i in range(N+1)]
def dfs(now, depth, path):
    if l[now] == []:
        if depthlist[now] < depth:
            depthlist[now] = depth
            pathlist[now] = path[:]

    else:
        for next in l[now]:
            dfs(next, depth+1, path+[now])

dfs(first, 1, [])

Submission status: Wrong Answer

Solution code:
#A
"""
n, a, b = map(int, input().split())
ab = n / 2
ansa = min(a, b)
ansb = max((a+b)-n, 0)
print(ansa,ansb)
"""

#B
"""
n = int(input())
a = input()
b = input()
c = input()
ans = 0
for i in range(n):
    bf = [a[i], b[i], c[i]]
    bf = set(bf)
    ans += len(bf) - 1
print(ans)
"""

#C 
"""
n = int(input())
ab = []
aba = []
abb = []
for i in range(n):
    a,b = map(int, input().split())
    ab.append([a + b, i])
    aba.append(a)
    abb.append(b)
ab.sort(reverse = True, key = lambda x:x[0])
ans = 0
for i in range(n):
    if i % 2 == 0:
        ans += aba[ab[i][1]]
    else:
        ans -= abb[ab[i][1]]
print(ans)
"""

#D
n, m = map(int, input().split())
ab = [[] for _ in range(n)]
for i in range(n + m - 1):
    a,b = map(int, input().split())
    ab[b-1].append(a-1)
ans = [-1 for i in range(n)]
rank = [-1 for _ in range(n)]
for i in range(n):
    if len(ab[i]) == 0:
        rank[i] = 1
        ans[i] = 0
        oya = i
for i in range(n):  
    if len(ab[i]) == 1:
        ans[i] = ab[i][0] + 1
        if ab[i][0] == oya:
            rank[i] = 2
        del ab[i][0]

cont = 0

while cont == 0:
    cont = 1
    for i in range(n):
        ran = -1
        if len(ab[i]) != 0:
            
            for k in ab[i]:
                ranb = max(ran, rank[k])
                if ran != ranb:
                    m = k
                ran = ranb
                if rank[k] == -1:
                    break
            else:

                rank[i] = rank[m] + 1
                ans[i] = m + 1
                ab[i] = []
                cont = 0

for i in ans:
    if i != 0:
        print(i)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
#A
"""
n, a, b = map(int, input().split())
ab = n / 2
ansa = min(a, b)
ansb = max((a+b)-n, 0)
print(ansa,ansb)
"""

#B
"""
n = int(input())
a = input()
b = input()
c = input()
ans = 0
for i in range(n):
    bf = [a[i], b[i], c[i]]
    bf = set(bf)
    ans += len(bf) - 1
print(ans)
"""

#C 
"""
n = int(input())
ab = []
aba = []
abb = []
for i in range(n):
    a,b = map(int, input().split())
    ab.append([a + b, i])
    aba.append(a)
    abb.append(b)
ab.sort(reverse = True, key = lambda x:x[0])
ans = 0
for i in range(n):
    if i % 2 == 0:
        ans += aba[ab[i][1]]
    else:
        ans -= abb[ab[i][1]]
print(ans)
"""

#D
n, m = map(int, input().split())
ab = [[] for _ in range(n)]
for i in range(n + m - 1):
    a,b = map(int, input().split())
    ab[b-1].append(a-1)
ans = [-1 for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(n):
    if len(ab[i]) == 0:
        rank[i] = 1
        ans[i] = 0
        oya = i
for i in range(n):  
    if len(ab[i]) == 1:
        ans[i] = ab[i][0]
        if ab[i][0] == oya:
            rank[i] = 2
        del ab[i][0]

cont = 0
while cont == 0:
    cont = 1
    for i in range(n):
        ran = -1
        if len(ab[i]) != 0:
            
            for k in ab[i]:
                ranb = max(ran, rank[k])
                if ran != ranb:
                    m = k
                ran = ranb
                if rank[k] == -1:
                    break
            else:
                rank[i] = rank[m] + 1
                ans[i] = m
                ab[i] = []
                cont = 0
for i in ans:
    if i != 0:
        print(i + 1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
#A
"""
n, a, b = map(int, input().split())
ab = n / 2
ansa = min(a, b)
ansb = max((a+b)-n, 0)
print(ansa,ansb)
"""

#B
"""
n = int(input())
a = input()
b = input()
c = input()
ans = 0
for i in range(n):
    bf = [a[i], b[i], c[i]]
    bf = set(bf)
    ans += len(bf) - 1
print(ans)
"""

#C 
"""
n = int(input())
ab = []
aba = []
abb = []
for i in range(n):
    a,b = map(int, input().split())
    ab.append([a + b, i])
    aba.append(a)
    abb.append(b)
ab.sort(reverse = True, key = lambda x:x[0])
ans = 0
for i in range(n):
    if i % 2 == 0:
        ans += aba[ab[i][1]]
    else:
        ans -= abb[ab[i][1]]
print(ans)
"""

#D
n, m = map(int, input().split())
ab = [[] for _ in range(n)]
for i in range(n + m - 1):
    a,b = map(int, input().split())
    ab[b-1].append(a-1)
ans = [-1 for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(n):
    if len(ab[i]) == 0:
        rank[i] = 1
        ans[i] = 0
        oya = i
for i in range(n):  
    if len(ab[i]) == 1:
        ans[i] = ab[i][0]
        if ab[i][0] == oya:
            rank[i] = 2
        del ab[i][0]

cont = 0
while cont == 0:
    cont = 1
    for i in range(n):
        ran = -1
        if len(ab[i]) != 0:
            
            for k in ab[i]:
                ranb = max(ran, rank[k])
                if ran != ranb:
                    m = k
                ranb = ran
                if rank[k] == -1:
                    break
            else:
                rank[i] = rank[m] + 1
                ans[i] = m
                ab[i] = []
                cont = 0
for i in ans:
    if i != 0:
        print(i + 1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:

from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)
pairents = [-1]*N

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    X[b-1] += 1

q = X.index(0)

Q = deque([q])
while Q:
    p = Q.popleft()
    for q in G[p]:
        if not searched[q]:
            searched[q] = searched[p] + 1
            Q.append(q)            
        elif searched[q] <= searched[p]:
            searched[q] = searched[p] + 1

for a in range(N):
    for b in G[a]:
        if searched[b] == searched[a] + 1:
            pairents[b] = a
for p in pairents:
    print(p+1)

Submission status: Wrong Answer

Solution code:
# import numpy as np

import sys
sys.setrecursionlimit(200000)


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

A, B = [], []
to = [[] for i in range(N)]

for _ in range(N + M - 1):
    q = input()
    a, b = list(map(int, q.split(" ")))
    A.append(a)
    B.append(b)
    to[a - 1].append(b - 1)


class Node:
    def __init__(self):
        self.parent = set()
        self.children = set()
        self.deep = 0
        self.res = 0


nodes = [Node() for _ in range(N + 1)]

for a, b in zip(A, B):
    nodes[b].parent.add(a)
    nodes[a].children.add(b)

root_num = int(list(set(A) - set(B))[0])


def traverse(root):
    # for p in root.parent:
    #     root.anc = root.anc.union(nodes[p].anc)
    #     root.anc = root.anc.union(nodes[p].parent)
    for c in root.children:
        if nodes[c].deep == 0:
            nodes[c].deep = max(nodes[c].deep, root.deep + 1)
            traverse(nodes[c])


traverse(nodes[root_num])

for i in range(1, N + 1):
    deep = nodes[i].deep
    if deep == 0:
        nodes[i].res = 0
    for p in nodes[i].parent:
        if nodes[p].deep == deep - 1:
            nodes[i].res = p
            break

for i in range(1, N + 1):
    print(nodes[i].res)


# for i in range(1, N + 1):
#     rm = []
#     for p in nodes[i].parent:
#         if p in nodes[i].anc:
#             rm.append(p)
#     for p in rm:
#         nodes[i].parent.remove(p)
#         nodes[p].children.remove(i)

# for i in range(1, N + 1):
#     if len(nodes[i].parent) == 0:
#         print(0)
#     else:
#         print(list(nodes[i].parent)[0])

Submission status: Wrong Answer

Solution code:
#A
"""
n, a, b = map(int, input().split())
ab = n / 2
ansa = min(a, b)
ansb = max((a+b)-n, 0)
print(ansa,ansb)
"""

#B
"""
n = int(input())
a = input()
b = input()
c = input()
ans = 0
for i in range(n):
    bf = [a[i], b[i], c[i]]
    bf = set(bf)
    ans += len(bf) - 1
print(ans)
"""

#C 
"""
n = int(input())
ab = []
aba = []
abb = []
for i in range(n):
    a,b = map(int, input().split())
    ab.append([a + b, i])
    aba.append(a)
    abb.append(b)
ab.sort(reverse = True, key = lambda x:x[0])
ans = 0
for i in range(n):
    if i % 2 == 0:
        ans += aba[ab[i][1]]
    else:
        ans -= abb[ab[i][1]]
print(ans)
"""

#D
n, m = map(int, input().split())
ab = [[] for _ in range(n)]
for i in range(n + m - 1):
    a,b = map(int, input().split())
    ab[b-1].append(a-1)
ans = [-1 for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(n):
    if len(ab[i]) == 0:
        rank[i] = 1
        ans[i] = 0
        oya = i
for i in range(n):  
    if len(ab[i]) == 1:
        ans[i] = ab[i][0]
        if ab[i][0] == oya:
            rank[i] = 2
        del ab[i][0]

cont = 0
while cont == 0:
    cont = 1
    for i in range(n):
        ran = -1
        if len(ab[i]) != 0:
            
            for k in ab[i]:
                ranb = max(ran, rank[k])
                if ran != ranb:
                    m = k
                ranb = ran
                if rank[k] == -1:
                    break
            else:
                rank[i] = rank[m] + 1
                ans[i] = m
                ab[i] = []
                cont = 0
for i in ans:
    print(i+1)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N+M-1)]

def f(n, parent):
    if start[n-1] >= 0:
        return
    start[n-1] = parent
    for i in range(N+M-1):
        if data[i][0] == n and start[data[i][1]-1] == -1:
            f(data[i][1], data[i][0])


for i in range(N):
    start = [-1]*N
    f(i+1, 0)
    if min(start) == 0:
        for i in start:
            print(i)
        exit()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import deque

N, M = map(int, input().split())
AB = []
for _ in range(N-1+M):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(key=lambda x: x[0])
BA = sorted(AB, key=lambda x: x[1])
AB_A = [a for a, b in AB]
BA_B = [b for a, b in BA]

# find root
root = 1
while True:
    i = bisect_left(BA_B, root)
    if BA_B[i] != root:
        break
    root = BA[i][0]

t_nl = [0] * (N + 1)
t_ln = [0] * (N + M + 1)
isdup_n = [True] * (N + 1)
par_n = [0] * (N + 1)

q = deque()
q.append((root, 0))
l = 1
while len(q):
    n, p = q.popleft()
    t_nl[n] = l
    t_ln[l] = n
    if par_n[n] == 0:
        par_n[n] = p
    else:
        par_n[n] = par_n[n] if t_nl[par_n[n]] > t_nl[p] else p
        l += 1
        continue
    i = bisect_left(AB_A, n)
    while i < len(AB_A) and AB_A[i] == n:
        q.append((AB[i][1], n))
        i += 1
    l += 1

for v in par_n[1:]:
    print(v)

Submission status: Wrong Answer

Solution code:
import queue

N, M = (int(i) for i in input().split())
G = [[] for i in range(N)]
R = [[] for i in range(N)]
for i in range(N+M-1):
    A, B = (int(i) for i in input().split())
    G[A-1].append(B-1)
    R[B-1].append(A-1)

for i in range(N):
    if len(R[i]) == 0:
        oya = i
        break

prev = [-1] * N
search = [False] * N
v = queue.Queue()
v.put(oya)
while not v.empty():
    now = v.get()
    if search[now]:
        continue
    if G[now]:
        for u in G[now]:
            prev[u] = now
            v.put(u)
    search[now] = True

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

Submission status: Wrong Answer

Solution code:
#A
"""
n, a, b = map(int, input().split())
ab = n / 2
ansa = min(a, b)
ansb = max((a+b)-n, 0)
print(ansa,ansb)
"""

#B
"""
n = int(input())
a = input()
b = input()
c = input()
ans = 0
for i in range(n):
    bf = [a[i], b[i], c[i]]
    bf = set(bf)
    ans += len(bf) - 1
print(ans)
"""

#C 
"""
n = int(input())
ab = []
aba = []
abb = []
for i in range(n):
    a,b = map(int, input().split())
    ab.append([a + b, i])
    aba.append(a)
    abb.append(b)
ab.sort(reverse = True, key = lambda x:x[0])
ans = 0
for i in range(n):
    if i % 2 == 0:
        ans += aba[ab[i][1]]
    else:
        ans -= abb[ab[i][1]]
print(ans)
"""

#D
n, m = map(int, input().split())
ab = [[] for _ in range(n)]
for i in range(n + m - 1):
    a,b = map(int, input().split())
    ab[b-1].append(a-1)
ans = [-1 for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(n):
    if len(ab[i]) == 0:
        rank[i] = 1
        ans[i] = 0
        oya = i
for i in range(n):  
    if len(ab[i]) == 1:
        ans[i] = ab[i][0]
        if ab[i][0] == oya:
            rank[i] = 2
        del ab[i][0]
print(ab)
cont = 0
while cont == 0:
    cont = 1
    for i in range(n):
        ran = -1
        if len(ab[i]) != 0:
            
            for k in ab[i]:
                ranb = max(ran, rank[k])
                if ran != ranb:
                    m = k
                ranb = ran
                if rank[k] == -1:
                    break
            else:
                rank[i] = rank[m] + 1
                ans[i] = m
                ab[i] = []
                cont = 0
for i in ans:
    print(i+1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())

par = [[] for i in range(n)]
op = [[]for i in range(n)]
for i in range(n+m-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    par[y].append(x)
    op[x].append(y)

res = [-1]*n
x = -1
print(par)
print(op)

for i in range(n):
    if len(par[i])==0:
        res[i] = 0
        x = i
        print(1)
        exit()
        break


used = [0]*n
used[x]=1
def g(y):
    for pe in par[y]:
        if used[pe]==0:
            return False
    return True
    
#xの下のusedとresを埋める
def f(z):
    for e in op[z]:
        if used[e]==0 and g(e):
            used[e]=1
            res[e]=z+1
            f(e)
f(x)
for i in range(n):
    print(res[i])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

N_dict = {k: 0 for k in range(1, N+1)}
N_set = set()

for i in range(N-1+M):
	A, B = map(int, input().split())
	if B not in N_set:
		N_dict[B] = A
		N_set.add(B)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
links = [tuple(map(int, input().split())) for k in range(N - 1 + M)]

high = [-1] * N
child = [set() for i in range(N)]
parent = [set() for i in range(N)]
res_p = [-1] * N
for s, v in links:
    s -= 1
    v -= 1
    parent[v].add(s)
    child[s].add(v)

def r_high(n):
    for c in child[n]:
        high[c] = max(high[n] + 1, high[c])


stack = []
done = set()
for n, p in enumerate(parent):
    if len(p) == 0:
        res_p[n] = 0
        done.add(n)
        high[n] = 0
        r_high(n)
        stack.append(n)
        break

while stack:
    root = stack.pop(0)
    set_c = child[root]
    for c in set_c:
        if c in done:
            continue

        parent[c] = {p for p in parent[c] if high[c] <= high[p] + 1}
        if len(parent[c]) == 1:
            res_p[c] = root + 1
            r_high(c)
            stack.append(c)

for r in res_p:
    print(r)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(N+M-1):
    u, v = map(int, input().split())
    adjL[u-1].append(v-1)
    indegs[v-1] += 1

num = 0
parents = [-1] * N
vRoot = [v for v in range(N) if indegs[v] == 0][0]
vNows = set([vRoot])
while vNows:
    isRem = False
    vNexts = set()
    for vNow in vNows:
        for v2 in adjL[vNow]:
            if parents[v2] != vNow:
                isRem = True
            parents[v2] = vNow
            vNexts.add(v2)
    vNows = vNexts
    if isRem:
        num += 1
        if num >= M:
            break

for v in range(N):
    print(parents[v] + 1)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
T = [[] for i in range(N)]
dupT = []
for i in range(N+M-1):
    A,B = list(map(int, input().split()))
    T[B-1].append(A)

# print("T:")
# print(T)

for k in range(N):
#     print("len of",k+1,"is",len(T[k]))
    while len(T[k]) > 1:
        cands = T[k]
        # print("cands:",cands)
        for c in cands:
            pares = T[c-1]
        #     print("pares:",pares)
            temp = 0
            try:
                for p in pares:
                    if p in cands:
                        temp = 1
                        break
            except:
                pass
            if temp == 0:
                T[k].remove(c)

for k in range(N):
    if len(T[k]) == 0:
        print(0)
    else:
        print(T[k][0])