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: Runtime Error

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 len(parent[v]) > 1:
            parent[v].remove(V)
        else:
            que.append([V, v])
for i in range(N):
    print(parent[i][0]+1)

Submission status: Runtime Error

Solution code:
from collections import deque

n, m = map(int, input().split())
parent = {i:[] for i in range(n)}
child = {i:[] for i in range(n)}
root = [i for i in range(n)]
for _ in range(n-1+m):
    a,b = map(int, input().split())
    child[a-1].append(b-1)
    parent[b-1].append(a-1)
    if b in root:
        root.remove(b)

root = root[0]

distance = {i:0 for i in range(n)}

queue = deque()
queue.append(root)
while queue:
    pos = queue.popleft()
    # print('pos',pos)
    children = child[pos]
    pos_dist = distance[pos]
    for c in children:
        # print('c,parent,dist',c,parent[c],distance[c])
        # if distance[c]<pos_dist+1:
        #     distance[c] = pos_dist+1
        parent[c] = pos
        # print('c,update',c, parent[c],distance[c])
        queue.append(c)
# print(distance)
# print(parent)

for i in range(n):
    if i == root:
        print(0)
    else:
        print(parent[i]+1)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b
from collections import deque

n, m = getMN()
class vertex():
    def __init__(self):
        self.number = 0
        self.dst = 0

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]
for i in range(m+n-1):
    m,n = getMN()
    parents[n].append(m)
    childs[m].append(n)
vtxs = [vertex() for i in range(n+2)]
d = deque()
for i ,x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

vtxs[n_root].dst = 0


def bfs(n_cur):
    #print(([v.dst for v in vtxs]))
    #c is pure integer
    #print("n_cur = {}".format(n_cur))
    v_cur = vtxs[n_cur]
    for c in childs[n_cur]:
        d.append(c)
        #print("c = {}".format(c))
        vtxs[c].dst = max(vtxs[c].dst, v_cur.dst+1)
    while(d):
        bfs(d.popleft())

bfs(n_root)

dsts = (([v.dst for v in vtxs]))

for plist in parents[1:]:
    if plist:
        cur = -1
        for p in plist:
            if dsts[p] > cur:
                cur = dsts[p]
                ans = p
        print(ans)
    else:
        print(0)

Submission status: Runtime Error

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:
            if len(parent[v]) > 1:
                parent[v].remove(V)
            else:
                visited[v] = 1
                que.append([V, v])
for i in range(N):
    print(parent[i][0]+1)

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

D = [0] * (n+1)
P = [0] * (n+1)

def dfs(p, i, depth):
    if depth > D[i]:
        D[i] = depth
        P[i] = p
    for t in T[i]:
        dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)

Submission status: Runtime Error

Solution code:
N,M =[int(i)for i in input().split()]
oya =[[]for i in range(N)]
ko =[[] for i in range(N)]
for _ in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    oya[B-1].append(A-1)
    ko[A-1].append(B-1)
tyouten =oya.index([])
rank =[[-1,-1]for _ in range(N)]
def keisan(num,no,bef):
    if rank[num][0] < no:
        rank[num]=[no,bef]
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
for i in rank:
    print(i[1]+1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(20000)

def dfs(temp):
    global dist, e, count_from, count_to
    global count, parent

    if count[temp] == count_from[temp]:
        for to in e[temp]:
            count[to] += 1
            temp_dist = dist[temp] + 1
            if temp_dist > dist[to]:
                parent[to] = temp
                dist[to] = temp_dist
            dfs(to)

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

count_from = [0] * N
count_to = [0] * N
e = [[] for _ in range(N)]

for i in range(N + M - 1):
    a, b = map(int, input().split())
    e[a - 1].append(b - 1)
    count_from[b - 1] += 1
    count_to[a - 1] += 1

start = 0
for i in range(N):
    if count_from[i] == 0:
        start = i
        break

dist = [0] * N
count = [0] * N
parent = [-1] * N

dfs(start)

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

Submission status: Runtime Error

Solution code:
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 = s[j][1]
            I = j
    print(I+1)

Submission status: Runtime Error

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, already):
    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:
        traverse(nodes[c])


traverse(nodes[root_num])

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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

def dfs(temp):
    global dist, e, count_from, count_to
    global count, parent

    if count[temp] == count_from[temp]:
        for to in e[temp]:
            count[to] += 1
            temp_dist = dist[temp] + 1
            if temp_dist > dist[to]:
                parent[to] = temp
                dist[to] = temp_dist
            dfs(to)

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

count_from = [0] * N
count_to = [0] * N
e = [[] for _ in range(N)]

for i in range(N + M - 1):
    a, b = map(int, input().split())
    e[a - 1].append(b - 1)
    count_from[b - 1] += 1
    count_to[a - 1] += 1

start = 0
for i in range(N):
    if count_from[i] == 0:
        start = i
        break

dist = [0] * N
count = [0] * N
parent = [-1] * N

dfs(start)

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

Submission status: Runtime Error

Solution code:
import numpy as np

class Tree(object):
    def __init__(self, edges):
        self.par = {}
        self.fix_d = {}
        for edge in edges:
            self.add(edge)

    def add(self, edge):
        r, b = edge
        if b not in self.par:
            self.par[b] = []
        self.par[b].append(r)

    def depth(self, node):
        if node in self.fix_d:
            return self.fix_d[node]
        if node not in self.par:
            self.fix_d[node] = 0
            return 0
        depthes = [self.depth(v) + 1 for v in self.par[node]]
        d = max(depthes)
        p = self.par[node][np.argmax(depthes)]
        self.par[node] = [p]
        self.fix_d[node] = d
        return d

    def rem(self):
        for node in self.par:
            if len(self.par[node]) > 1:
                self.depth(node)

    def parent(self, node):
        if node not in self.par:
            return 0
        return self.par[node][0]


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

t = Tree(edges)
t.rem()
for i in range(1, n + 1):
    print(t.parent(i))

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=[int(i) for i in input().split(" ")]

G=np.zeros((N,N))
for i in range(N+M-1):
    A,B=[int(j)-1 for j in input().split(" ")]
    G[A][B]=1
for i in range(M):
    x=np.sum(G,axis=0).argmax()
    y=np.sum(G,axis=1).argmax()
    G[y][x]-=1

for l in G.T:
    if np.sum(l)==0:
        print("0")
    else:
        print(l.argmax()+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=[int(i) for i in input().split(" ")]

G=np.zeros((N,N))
for i in range(N+M-1):
    A,B=[int(j)-1 for j in input().split(" ")]
    G[A][B]=1
print(G)
for i in range(M):
    x=np.sum(G,axis=0).argmax()
    y=np.sum(G,axis=1).argmax()
    G[y][x]-=1

print(G)
for l in G.T:
    if np.sum(l)==0:
        print("0")
    else:
        print(l.argmax()+1)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
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: Runtime Error

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s):
    global ans
    for t in g[s]:
        if ans[t] is None:
            ans[t] = s + 1
            dfs2(t)


ans = [None] * N
s = dfs1(0)
dfs2(s)

for x in ans:
    print(x)

Submission status: Runtime Error

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: Runtime Error

Solution code:
from copy import deepcopy
N, M = [int(a) for a in input().split()]
# N, M = 6, 3
all_list = list()
for i in range(N):
    all_list.append([[], []])
# inputs = ["2 1", "2 3", "4 1", "4 2", "6 1", "2 6", "4 6", "6 5"]
for i in range(N + M - 1):
    a, b = [int(a) for a in inputs[i].split()]
    all_list[b-1][0].append(a)
    all_list[b-1][1].append(a)
    if len(all_list[b-1][0]) > 1:
        dummy_parent = deepcopy(all_list[b-1][0])
        for parent in dummy_parent:
            for other_parent in all_list[parent-1][0]:
                if parent != other_parent and other_parent in all_list[parent-1][1]:
                    try:
                        all_list[b-1][0].remove(other_parent)
                    except:
                        pass
    for dup in all_list:
        if a in dup[0] and b in dup[0]:
            dup[0].remove(a)
    # print(all_list)
for i in range(N):
    try:
        print(str(all_list[i][0][0]))
    except:
        print(0)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

to_par = {i: [] for i in range(1, N+1)}
to_chi = {i: [] for i in range(1, N+1)}
con_list = []
for _ in range(N - 1 + M):
    a, b = ds_in()
    to_par[b].append(a)


def find_all_parents(child):
    """
    child : int
    """
    all_parents = []
    for p in to_par[child]:
        all_parents.append(p)
        all_parents.extend(find_all_parents(p))
    all_parents = list(set(all_parents))
    return all_parents


parents_dict = {i: find_all_parents(i) for i in range(1, N+1)}

ans = {i: 0 for i in range(1, N+1)}
for child in range(1, N+1):
    par_cand = to_par[child]
    all_par = []
    for p in par_cand:
        all_par.extend(parents_dict[p])
    all_par = list(set(all_par))
    for p in par_cand:
        if p not in all_par:
            ans[child] = p
            break

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


# IPython.embed()

Submission status: Runtime Error

Solution code:
N,M =[int(i)for i in input().split()]
oya =[[]for i in range(N)]
ko =[[] for i in range(N)]
for _ in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    oya[B-1].append(A-1)
    ko[A-1].append(B-1)
tyouten =oya.index([])
rank =[-1]*N
def keisan(num,no):
    rank[num] =max(rank[num],no)
    for i in ko[num]:
        keisan(i,no+1)

keisan(tyouten,0)

for k,i in enumerate(oya):
    if i ==[]:
        print(0)
    else:
        for j in i:
            if rank[k]==rank[j]+1:
                print(j+1)

Submission status: Runtime Error

Solution code:
# coding: utf-8
n,m=map(int,input().split())
g=[set() for i in range(n)]
revg=[set() for i in range(n)]
for i in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].add(b)
    revg[b].add(a)
p=0
while True:
    if len(revg[p])==0:
        break
    for nxt in revg[p]:
        p=nxt
        break
ans=[-1 for i in range(n)]
ans[p]=0
def check(pos):
    if len(g[pos])==0:
        return
    for nxt in g[pos]:
        revg[nxt].remove(pos)
    for nxt in g[pos]:
        if len(revg[nxt])==0 and ans[nxt]==-1:
            ans[nxt]=pos+1
            check(nxt)
check(p)
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
revEdges = [[] for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    revEdges[b].append(a)

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = n
    index = n
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = fr

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

Submission status: Runtime Error

Solution code:
N,M =[int(i)for i in input().split()]
oya =[[]for i in range(N)]
ko =[[] for i in range(N)]
dabu =set()
for i in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    oya[B-1].append(A-1)
    ko[A-1].append(B-1)
    if len(oya[B-1]) > 1:
        dabu.add(B-1)
print(oya,ko)
tyouten =oya.index([])
rank =[-1]*N
def keisan(num,no):
    rank[num] =max(rank[num],no)
    for i in ko[num]:
        keisan(i,no+1)

keisan(tyouten,0)
for k,i in enumerate(oya):
    if i ==[]:
        print(0)
    else:
        for j in i:
            if rank[k]==rank[j]+1:
                print(j+1)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
G1=[[] for i in range(N)]
G2=[[] for i in range(N)]
not_root=[False]*N
for i in range(N+M-1):
  a,b=map(int,input().split())
  G1[a-1].append(b-1)
  G2[b-1].append(a-1)
  not_root[b-1]=True
for i in range(N):
  if not not_root[i]:
    root=i
    break
Tree=[-2]*N
Tree[root]=-1
def dfs(x):
  for b in G1[x]:
    if Tree[b]>=-1:
      continue
    flag=0
    for a in G2[b]:
      if Tree[a]<-1:
        flag=1
        break
    if flag==0:
      Tree[b]=x
      dfs(b)
dfs(root)
for i in range(N):
  print(Tree[i]+1)

Submission status: Runtime Error

Solution code:
# coding: utf-8

import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

II = lambda: int(input())
MI = lambda: map(int, input().split())



def main():
    N, M = MI()
    node_parents = [set() for _ in range(N)]
    node_children = [set() for _ in range(N)]
    for i in range(N - 1 + M):
        a, b = MI()
        node_parents[b-1].add(a-1)
        node_children[a-1].add(b-1)

    for i in range(N):
        if len(node_parents[i]) == 0:
            Root = i
            break

    leaves = set()
    visited = set()
    def find_leaf(v):
        if v in visited: return
        visited.add(v)
        if len(node_children[v]) == 0:
            leaves.add(v)
        for c in node_children[v]:
            find_leaf(c)
    find_leaf(Root)


    def find_root_path(v):
        if v == Root:
            return [[v]]
        path = []
        for p in node_parents[v]:
            ppath = find_root_path(p)
            if ppath is not None:
                path.extend(ppath)
        if len(path) == 0:
            return None
        for p in path:
            p.append(v)
        return path

    def find_longest_path(paths):
        ia, l = 0, 0
        for i, p in enumerate(paths):
            if len(p) > l:
                l = len(p)
                ia = i
        return ia

    for l in leaves:
        paths = find_root_path(l)
        longest_path_i = find_longest_path(paths)
        lp = paths.pop(longest_path_i)
        lp_edges = [(lp[i], lp[i + 1]) for i in range(len(lp) - 1)]
        for path in paths:
            for i in range(len(path) - 1):
                edge = (path[i], path[i + 1])
                if edge not in lp_edges and edge[0] in node_parents[edge[1]]:
                    node_parents[edge[1]].remove(edge[0])

    for i in range(N):
        if i == Root:
            print(0)
        else:
            print(node_parents[i].pop() + 1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# import numpy as np
import sys
sys.setrecursionlimit(1e+6)

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 c in root.children:
        traverse(nodes[c])


traverse(nodes[root_num])

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: Runtime Error

Solution code:
from copy import deepcopy
N, M = [int(a) for a in input().split()]
all_list = [[], []] * N
for i in range(N + M - 1):
    a, b = [int(a) for a in input().split()]
    all_list[b-1][0].append(a)
    all_list[b-1][1].append(a)
    if len(all_list[b-1][0]) > 1:
        dummy_parent = deepcopy(all_list[b-1][0])
        for parent in dummy_parent:
            for other_parent in all_list[b-1][0]:
                if other_parent in all_list[b-1][1]:
                    all_list[b-1][0].remove(other_parent)
    for dup in all_list:
        if a in dup[0] and b in dup[0]:
            dup[0].remove(a)
for i in range(N):
    print(str(all_list[i][0][0]))

Submission status: Runtime Error

Solution code:
# import numpy as np

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 c in root.children:
        traverse(nodes[c])


traverse(nodes[root_num])

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: Runtime Error

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 = []
while queue:
  if c in visited:
    continue
  c = queue.pop(0)
  visited.append(c)
  if c in xs:
    for x in xs[c]:
      used[x-1] = c
      queue.append(x)

for x in used:
  print(x)

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
P_cand = [set() for _ in range(N + 1)]
for a, b in AB:
    G[a].add(b)
    P_cand[b].add(a)
for p in range(1, N):
    if len(P_cand[p]) == 0:
        break
D = [[0, -1] for _ in range(N + 1)]
D[p] = [0, 0]


def dfs(p):
    for _ in range(len(G[p])):
        for c in G[p]:
            if D[c][1] < D[p][1] + 1:
                D[c][1] = D[p][1] + 1
                D[c][0] = p
                dfs(c)


dfs(p)
[print(_[0]) for _ in D[1:]]

Submission status: Runtime Error

Solution code:
import numpy as np

class Tree(object):
    def __init__(self, edges):
        self.par = {}
        for edge in edges:
            self.add(edge)

    def add(self, edge):
        r, b = edge
        if b not in self.par:
            self.par[b] = []
        self.par[b].append(r)

    def depth(self, node):
        if node not in self.par:
            return 0
        depthes = [self.depth(v) + 1 for v in self.par[node]]
        d = max(depthes)
        p = self.par[node][np.argmax(depthes)]
        self.par[node] = [p]
        return d

    def rem(self):
        for node in self.par:
            if len(self.par[node]) > 1:
                self.depth(node)

    def parent(self, node):
        if node not in self.par:
            return 0
        return self.par[node][0]


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

t = Tree(edges)
t.rem()
for i in range(1, n + 1):
    print(t.parent(i))

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    AB.append([a,b])
    
acount = 0
bcount = 0
for i in range(N):
    if max(A) >= max(B):
        indexes = [j for j, x in enumerate(A) if x == max(A)]
        L = len(indexes)
        ab = []
        MAX = 0
        for k in range(L):
            if MAX <= B[indexes[k]]:
                MAX = B[indexes[k]]
                Index = indexes[k]
        
        if i%2 == 0:
            acount+=A.pop(Index)
            trash = B.pop(Index)
        else:
            bcount+=B.pop(Index)
            trash = A.pop(Index)
    else:
        indexes = [j for j, x in enumerate(B) if x == max(B)]
        L = len(indexes)
        ab = []
        MAX = 0
        for k in range(L):
            if MAX <= A[indexes[k]]:
                MAX = A[indexes[k]]
                Index = indexes[k]
        
        if i%2 == 0:
            acount+=A.pop(Index)
            trash = B.pop(Index)
        else:
            bcount+=B.pop(Index)
            trash = A.pop(Index)
print(acount-bcount)

Submission status: Runtime Error

Solution code:
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 = 0
        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
for i in range(N):
    print(trees[i+1].current_parent)

Submission status: Runtime Error

Solution code:
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 = 0
        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!=parent_no:
            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
for i in range(N):
    print(trees[i+1].current_parent)