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:
n,m = map(int, input().split())

s = [[] for _ in range(n)]
for i in range(n+m-1):
    c,d = map(int,input().split())
    s[d-1].append(c-1)

for i in range(n):
    if len(s[i]) == 1:
        print(s[i][0] +1)
    elif len(s[i]) == 0:
        print(0)
    else:
        count = 0
        for j in s[i]:
            if count < len(s[j]):
                count = len(s[j])
                check = j
        print(check+1)

Submission status: Wrong Answer

Solution code:
def topological_sort(V, to):
    cnt = [0]*V
    s = []
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = []
    for i in range(V):
        if cnt[i] == 0:
            Q.append(i)
    while len(Q) > 0:
        i = Q[0]
        del Q[0]
        s.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:	Q.append(k)
    return s

N,M = map(int,input().split())
to = [[] for i in range(N)]
From = [[] for i in range(N)]
for i in range(N-1+M):
    x, y = list(map(int,input().split()))
    to[x-1].append(y-1)
    From[y-1].append(x-1)
s = topological_sort(N, to)
s = [(s[i],i) for i in range(N)]
s.sort()
for i in range(N):
    k = -1
    I = -1
    for j in From[i]:
        if k < s[j][1]:
            k = j
            I = j
    print(I+1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
number = [[0, 0] for i in range(n)]
tree = [[] for i in range(n)]
for i in range(n - 1 + m):
    a, b = map(int, input().split())
    tree[b - 1].append(a)
nagasa = []
for i in range(n):
    nagasa.append((i, len(tree[i])))
nagasa = sorted(nagasa, key=itemgetter(1))
for j in range(n):
    i = nagasa[j][0]
    if len(tree[i]) == 1:
        number[i] = [tree[i][0], number[tree[i][0] - 1][1] + 1]
    elif len(tree[i]) == 0:
        number[i] = [0, 0]
    else:
        kari = []
        m = 0
        for k in tree[i]:
            kari.append((k, number[k - 1][1] + 1))
            m = max(m, number[k - 1][1] + 1)
        for k in kari:
            if k[1] == m:
                number[i] = k
                break
for i in number:
    print(i[0])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() 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)]
mod = 1000000007

#A
"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""

#B
"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""

#C
"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""

#D
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
l = []
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
d = [[] for i in range(n)]
for a,b in c:
    v[a].append(b)
    d[b].append(a)
    ins[b] +=1
s = []
for i in range(n):
    if ins[i] == 0:
        s.append(i)
while s:
    x = s.pop(0)
    l.append(x)
    le = len(v[x])
    for i in range(le):
        y = v[x].pop(0)
        ins[y] -= 1
        if ins[y] == 0:
            s.append(y)
print(l)
"""
key = [l.index(i) for i in range(n)]
key.append(-1)
ans = [-1 for i in range(n)]
for i in range(n):
    if len(d[i]) != 0:
        ans[i] = n
        for j in d[i]:
            if key[j] > key[ans[i]]:
                ans[i] = j
for i in ans:
    print(i+1)
"""
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys

sys.setrecursionlimit(200000)
def nextis(now_node_i, hierarchy):
    for next_node_i in nodes[now_node_i]["children"]:
        if touched[next_node_i]["touched"] is False:
            touched[next_node_i]["touched"]=True
            touched[next_node_i]["parent"] = now_node_i
            touched[next_node_i]["hierarchy"] = hierarchy
            nextis(next_node_i, hierarchy+1)
        else:
            if hierarchy > touched[next_node_i]["hierarchy"]:
                touched[next_node_i]["parent"] = now_node_i
                touched[next_node_i]["hierarchy"] = hierarchy
        

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

nodes = [{"parents":[],"children":[]} for _ in range(n)]
for edge in range(n+m-1):
    a,b = map(int,input().split())
    nodes[a-1]["children"].append(b-1)
    nodes[b-1]["parents"].append(a-1)

# 親を探す
root=None
for i, node in enumerate(nodes):
    if node["parents"]==[]:
        #コード上の番地
        root=i
touched = [{"touched":False,"parent":None,"hierarchy":None} for _ in range(n)]
touched[root]["touched"]=True
nextis(root,0)
for i in range(n):
    if touched[i]["parent"] is None:
        print(0)
    else:
        print(touched[i]["parent"]+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def main():
    n, m = get_int_list()
    A = []
    B = []
    for _ in range(n - 1 + m):
        a, b = get_int_list()
        A.append(a)
        B.append(b)

    root = (set(A) - set(B)).pop()
    graph = defaultdict(list)
    for a, b in zip(A, B):
        graph[a].append(b)
    known = {root}
    deq = deque([root])
    added = set()
    cnt = 0
    while cnt < m:
        parent = deq.popleft()
        children = graph[parent]
        for c in children:
            if c in known:
                added.add(c)
                cnt += 1
                continue
            known.add(c)
            deq.append(c)
    parents = [0] * n
    deq = deque([root])
    cnt = 1
    while cnt < n:
        parent = deq.popleft()
        children = graph[parent]
        for c in children:
            if c in added:
                added.difference_update({c})
                continue
            parents[c-1] = parent
            cnt += 1
            deq.append(c)
    for parent in parents:
        print(parent)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys
sys.setrecursionlimit(200000)

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

A, B = [], []

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


class Node:
    def __init__(self):
        self.parent = set()
        self.anc = set()
        self.children = set()


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 i in range(1, N + 1):
    traverse(nodes[i])
for i in range(1, N + 1):
    traverse(nodes[i])

invalid = set()
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:
from collections import deque

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

v = [[] for i in range(N + 1)]
vin = [0 for i in range(N + 1)]

parent = [0 for i in range(N + 1)]
visited = [False for i in range(N + 1)]

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

Q = deque()
for i in range(1, N + 1):
    if vin[i] == 0:
        Q.append((i, 0))
        break

while len(Q) != 0:
    now, pa = Q.popleft()
    parent[now] = pa
    if visited[now]:
        continue
    for i in v[now]:
        Q.append((i, now))
    visited[now] = True

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() 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)]
mod = 1000000007

#A
"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""

#B
"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""

#C
"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""

#D
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
l = []
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
d = [[] for i in range(n)]
for a,b in c:
    v[a].append(b)
    d[b].append(a)
    ins[b] +=1
s = []
for i in range(n):
    if ins[i] == 0:
        s.append(i)
while s:
    x = s.pop(0)
    l.append(x)
    le = len(v[x])
    for i in range(le):
        y = v[x].pop(0)
        ins[y] -= 1
        if ins[y] == 0:
            s.append(y)
print(l)
key = [l.index(i) for i in range(n)]
key.append(-1)
ans = [-1 for i in range(n)]
for i in range(n):
    if len(d[i]) != 0:
        ans[i] = n
        for j in d[i]:
            if key[j] > key[ans[i]]:
                ans[i] = j
for i in ans:
    print(i+1)

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[[] for i in range(n+1)]
l=[list(map(int,input().split())) for i in range(n+m-1)]
for i in range(n+m-1):
    s[l[i][1]].append(l[i][0])
lis=[0 for _ in range(n)]
for i in range(1,n+1):
    lis[i-1]=len(s[i])
#print(s,lis)
for i in range(1,n+1):
    if lis[i-1]==0:
        print('0')
    else:
        ans=0
        cnt=0
        for j in range(lis[i-1]):
            a=lis[s[i][j]-1]
            #print(j,a)
            if cnt<=a:
                ans=s[i][j]
                cnt=a
        print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[[] for i in range(n+1)]
l=[list(map(int,input().split())) for i in range(n+m-1)]
for i in range(n+m-1):
    s[l[i][1]].append(l[i][0])
lis=[0 for _ in range(n)]
for i in range(1,n+1):
    lis[i-1]=len(s[i])
print(s,lis)
for i in range(1,n+1):
    if lis[i-1]==0:
        print('0')
    else:
        ans=0
        cnt=0
        for j in range(lis[i-1]):
            a=lis[s[i][j]-1]
            #print(j,a)
            if cnt<=a:
                ans=s[i][j]
                cnt=a
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        parent[i] = [-1]
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    que.append([root, v])
    if len(parent[v]) > 1:
        parent[v].remove(root) 
while que:
    u, V = que.popleft()
    for v in path[V]:
        if visited[v] == 0:
            visited[v] = 1
            que.append([V, v])
            if len(parent[v]) > 1:
                parent[v].remove(V)
for i in range(N):
    print(parent[i][0]+1)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    # 負の値はルートで集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        while self.table[x] >= 0:
            # 根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:  # 根が異なる場合
            if self.table[s1] != self.table[s2]:  # グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                # グラフの長さが同じ場合,どちらを根にしても変わらない
                # その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return


n, m = [int(i) for i in input().split()]
union = UnionFind(n)
parents = [-1 for _ in range(n)]
for i in range(n+m-1):
    a, b = [int(i) - 1 for i in input().split()]
    if parents[b] == -1 and union.find(a) != union.find(b):
            # print("par:{}".format(parents))
            union.union(a, b)
            parents[b] = a
for _par in parents:
    if _par == -1:
        print(0)
    else:
        print(_par+1)

Submission status: Wrong Answer

Solution code:
# from collections import namedtuple
# Node = namedtuple("Node", "in, out")
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N+M-1)]
ine = [[] * N for _ in range(N)]
oute = [[] * N for _ in range(N)]
for a, b in AB:
    ine[b-1].append(a-1)
    oute[a-1].append(b-1)
root = ine.index([])
v = [len(e) for e in ine]
print(v)
ans = [0] * N
q = [(root, n) for n in oute[root]]
while q:
    nq = []
    for p, n in q:
        v[n] -= 1
        if v[n] == 0:
            ans[n] = p + 1
            nq += [(n, nn) for nn in oute[n]]
    q = nq

print("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N, M = map(int, input().split())

edge = dd(set)
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
root = parent.index(0)

parent2 = [-1] * (N+1)
queue = set([root])
while len(queue):
  nq = set()
  for n in queue:
    for c in edge[n]:
      if parent2[c] == -1:
        nq.add(c)
      # 深いところでたどり着いたので、必ず置き換えてよい
      parent2[c] = n
  queue = nq

for i in range(1, N+1):
  print(parent2[i] if parent2[i] > 0 else 0)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys
sys.setrecursionlimit(200000)

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

A, B = [], []

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


class Node:
    def __init__(self):
        self.parent = set()
        self.anc = set()
        self.children = set()


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 i in range(1, N + 1):
    traverse(nodes[i])

invalid = set()
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:
N, M = map(int, input().split())
xs = {}
used = [0] * N
for i in range(N+M-1):
  a, b = map(int, input().split())
  used[b-1] = 1
  if a in xs:
  	xs[a].append(b)
  else:
    xs[a] = [b]
 
root = used.index(0)+1
queue = [root]
visited = [0]*N
while queue:
  c = queue.pop(0)
  if visited[c-1] == 1:
    continue
  visited[c-1] = 1
  if c in xs:
    for x in xs[c]:
      used[x-1] = c
      queue.append(x)
 
for x in used:
  print(x)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 5 + 100)

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

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

while q:
    v, p = q.popleft()
    if parents[v] != -1:
        parents[v] = p
        continue
    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 sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, m = li()
graph = [[] for _ in range(n)]

searched = [False]*n
ins = [0]*n
par = [-1]*n

for _ in range(n-1+m):
    a,b = li_()
    graph[a].append(b)
    ins[b] += 1
    
# 入次数が最も少ない頂点を選ぶ
inmin = float('inf')
start = -1
for i in range(n):
    if ins[i] < inmin:
        inmin = ins[i]
        start = i

par[start] = 0
searched[start] = True
cut = []

def dfs(node):
    for child in graph[node]:
        if searched[child]:
            cut.append([node, child])
        
        else:
            searched[child] = True
            par[child] = node+1
            
            dfs(child)

dfs(start)


def lca(p,q):
    p_parents = set([p])
    cur = p

    while par[cur] > 0:
        cur = par[cur]-1
        p_parents.add(cur)

    cur = q
    while cur not in p_parents:
        cur = par[cur]-1
        
    lca = cur
    
    return lca
    

for parent, child in cut:
    l = lca(parent, child)
    if l != parent:
        par[child] = parent+1
            
for idx, pi in enumerate(par):
    print(pi)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
n = {}
for i in range(N):
	n[i + 1] = 0
for i in range(N - 1 + M):
	A, B = map(int, input().split())
	AB.append((A, B))
	n[B] += 1
ans = {}
for A, B in AB:
	if B in ans:
		if n[A] > n[ans[B]]:
			ans[B] = A
	else:
		ans[B] = A
for i in range(1, N + 1):
	if i in ans:
		print(ans[i])
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000000)

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

AB = [tuple(map(int, input().split())) for _ in range(N + M - 1)]

dprint = print


class Tree:
    def __init__(self, n):
        self.parent = set()
        self.child = set()
        self.rank = -1
        self.current_parent = -1
        self.n = n

    def add_parent(self, i):
        self.parent.add(i)

    def add_child(self, i):
        self.child.add(i)

    def update_rank(self, v, parent_no):
        if self.rank >= v:
            return
        self.rank = v
        if self.current_parent != -1 and self.current_parent in self.parent:
            self.parent.remove(self.current_parent)
            trees[parent_no].child.remove(self.n)
        self.current_parent = parent_no
        for t in tuple(self.child):
            trees[t].update_rank(v + 1, self.n)

    def __repr__(self):
        return "child" + str(self.child) + "rank:" + str(self.rank) + " p:" + str(self.current_parent)


trees = [Tree(i) for i in range(N + 1)]
ans = [-1 for _ in range(N + 1)]
for a, b in AB:
    trees[a].add_child(b)
    trees[b].add_parent(a)

for i, t in enumerate(trees):
    if i != 0 and not t.parent:
        trees[0].add_child(i)
        trees[i].add_parent(0)
        trees[0].update_rank(0, 0)
        ans[i] = 0
        break
# print(trees)
for i in range(N):
    print(trees[i + 1].current_parent)

Submission status: Wrong Answer

Solution code:
print(0)
print(1)
print(2)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        ans[i] = -1
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    que.append([root, v])
while que:
    u, V = que.popleft()
    for v in path[V]:
        if visited[v] == 0:
            visited[v] = 1
            que.append([V, v])
        if visited[v] == 1 and ans[v] != V:
            que.append([V, v])
        ans[v] = V

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        ans[i] = -1
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    que.append([root, v])
while que:
    u, V = que.popleft()
    for v in path[V]:
        ans[v] = V
        if visited[v] == 0:
            visited[v] = 1
            que.append([V, v])

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
N, M = map(int, input().split())

edge = dd(set)
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
root = parent.index(0)

parent2 = [-1] + [0] * N
queue = set([root])
while len(queue):
  nq = set()
  for n in queue:
    for c in edge[n]:
      if parent2[c] == 0:
        nq.add(c)
      parent2[c] = n
  queue = nq

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None

def sigma_(a, b, n):
    return (a + b) * n // 2

def main():
    N, M = li_input()
    V = [li_input() for _ in range(N+M-1)]

    # print("N,M", N, M)
    # print("V", V)

    # 根を求める
    distV = []
    for v in V:
        distV.append(v[1])

    distV = list(set(distV))
    root = sigma_(1, N, N) - sum(distV)

    # print("root", root)

    # 順に辿る
    A = [0] * N

    parent_nodes = [root]
    while len(parent_nodes) != 0:
        new_parent_nodes = []
        i = 0
        while i < len(V):
            start, end = V[i]

            if start in parent_nodes:
                A[end-1] = start
                new_parent_nodes.append(end)
                
                # すでに見つかったノードを消す
                j = i+1
                while j < len(V):
                    if V[j][1] == end:
                        del V[j]
                    else:
                        j += 1
                
            i += 1

        parent_nodes = new_parent_nodes

    for a in A:
        print(a)

                


main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify

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

    for i in range(n):
        if isRoot[i]:
            root = i
            break
    INF = 10 ** 20
    stack = [(0, root, -1)]
    heapify(stack)
    height = [-INF] * n
    parent = [None] * n
    def search(stack):
        score, node, par = heappop(stack)
        print(score, node, par)
        if -score > height[node]:
            height[node] = -score
            parent[node] = par
            for to in edges[node]:
                heappush(stack,(score - 1, to, node))

    while stack:
        search(stack)

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

main()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n, m = li()
graph = [[] for _ in range(n)]

searched = [False]*n
ins = [0]*n
par = [-1]*n

for _ in range(n-1+m):
    a,b = li_()
    graph[a].append(b)
    ins[b] += 1
    
# 入次数が最も少ない頂点を選ぶ
inmin = float('inf')
start = -1
for i in range(n):
    if ins[i] < inmin:
        inmin = ins[i]
        start = i

par[start] = 0
searched[start] = True

def dfs(node):
    for child in graph[node]:
        if not searched[child]:
            searched[child] = True
            par[child] = node+1
            
            dfs(child)

dfs(start)
            
for idx, pi in enumerate(par):
    print(pi)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 100)

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

parent = [-1] * n
depth = [-1] * n


def dfs(v, p, d):
    # print(v, p, d, parent, depth)
    if depth[v] != -1:
        if depth[v] < d:
            parent[v] = p
            depth[v] = d
        return
    parent[v] = p
    depth[v] = d
    for c in links[v]:
        dfs(c, v, d + 1)


dfs(root, -1, 0)

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