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 numpy import argmax, argmin
n,m = map(int, input().split())

l = []
for _ in range(n):
    l.append([])

j = set()
for _ in range(n-1+m):
    a,b = map(int, input().split())
    l[b-1].append(a)
    j.add(a-1)


for i in range(n):
    z = set()
    for q in range(n):
        if q+1 not in j and i != q:
            for pq in range(len(l[q])):
                z.add(l[q][pq])

    p = 0
    while len(l[i]) > 1:
        if l[i][p] in z:
            l[i].remove(l[i][p])
        else:
            p += 1

for i in range(n):
    if len(l[i]) != 0:
        print(l[i][0])
    else:
        print(0)

Submission status: Runtime Error

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 any(edge_to[i]) and not any(edge_from[i]):
        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 not any(edge_from[child]):
                result[child] = p
                next.append(child)
    if not any(next_):
        break
    parent = next_.copy()

for x in result:
    print(x + 1)

Submission status: Runtime Error

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)

for i in range(N):
    if any(edge_to[i]) and not any(edge_from[i]):
        root = i
        break

result[root] = -1
parent = [root]
while True:
    next = []
    for p in parent:
        for child in edge_to[p]:
            edge_from[child].remove(p)
            if not any(edge_from[child]):
                result[child] = p
                next.append(child)
    if not any(next):
        break
    parent = next.copy()

for x in result:
    print(x + 1)

Submission status: Runtime Error

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):
    global used
    global res
    for i in range(len(down[z])):
        if used[down[z][i]]==0 and g(down[z][i]):
            used[down[z][i]]=1
            res[down[z][i]]=z+1
            f(down[z][i])
f(root)
for i in range(n):
    print(res[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            if len(an[el]) != 0:
                ret.append(an[el])
            else:
                ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        ans = an[a]
        ans.append(a)
        if all(k in ans for k in l):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

parent = [[] for _ in range(N)]
an = [[] for _ in range(N)]


# 入力
for _ in range(N+M-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[b] += 1
    parent[b].append(a)

# 先祖を作る
for i in range(N):
    an[i] = anscestor(i, parent)

for i in range(N):
    if nodes[i] >= 2:
        parent[i] = check(parent[i], parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

for i in parent:
    print(i)

Submission status: Runtime Error

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):
    global used
    global res
    for e in down[z]:
        E = e
        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: Runtime Error

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):
    global used
    global res
    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: Runtime Error

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

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


N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]

for _ in range(N + M - 1):
    u, v = [int(elem) - 1 for elem in fin().split()]
    adj[u].append(v)

inv_adj = [[] for _ in range(N)]
for u, neighbors in enumerate(adj):
    for v in neighbors:
        inv_adj[v].append(u)

topo = []
visited = [False] * N

def dfs_visit(node):
    for neighbor in adj[node]:
        if visited[neighbor]:
            continue
        visited[neighbor] = True
        dfs_visit(neighbor)
    topo.append(node)
    return

for node in range(N):
    if not visited[node]:
        visited[node] = True
        dfs_visit(node)

topo = topo[::-1]

parent = [-1] * N
order = dict()
order[topo[0]] = 0
for number, node in enumerate(topo[1:], start=1):
    neighbors = inv_adj[node]
    correct_parent = -1
    for neighbor in neighbors:
        if neighbor in order and order[neighbor] > correct_parent:
            correct_parent = order[neighbor]
    parent[node] = correct_parent
    order[node] = number

order_to_number = {v: k + 1 for k, v in order.items()}
order_to_number[-1] = 0

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

Submission status: Runtime Error

Solution code:
# cook your dish here
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
        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: Runtime Error

Solution code:
# cook your dish here
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
        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:
            if g(e):
                if e<=len(used) and e <= len(res):
                    used[e]=1
                    res[e]=z+1
                    f(e)

f(x)

for i in range(n):
    print(res[i])

Submission status: Runtime Error

Solution code:
giveup

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 = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Submission status: Runtime Error

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
        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:
            if g(e):
                used[e]=1
                res[e]=z+1
                f(e)

f(x)

for i in range(n):
    print(res[i])

Submission status: Runtime Error

Solution code:
# cook your dish here
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
        break


used = [0]*n
used[x]=1
def g(y):
    if len(par[y])==0:
        return True
    for pe in par[y]:
        if used[pe]==0:
            return False
    return True
    
#xの下のusedとresを埋める
def f(z):
    if len(op[z])>=1:
        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: Runtime Error

Solution code:
class Node(object):
    def __init__(self,point):
        self.point=point
        self.child=[]
        self.parent=[]
    def addpar(self,parent):
        self.parent.append(parent)
    def addchi( self,child ):
        self.child.append(child)
    def bigdaddy( self ):
        return True if len(self.parent)>1 else False

    def __str__(self):
        return 'node:{0} parents:{1} childs{2} '.format(self.point,self.parent,self.child)

N,M=map(int,input().split())
nodes=[Node(i) for i in range(1,N+1)]

keys=[]
for i in range(N-1+M):
    a,b=map(int,input().split())
    nodes[a-1].addchi(b)
    nodes[b-1].addpar(a)
    if nodes[b-1].bigdaddy():
        if b-1 not in keys:
            keys.append(b-1)


def solve(key,nodes,root,sticks=-1,dist=0,start=False):
    #print(nodes[key])
    if key+1 ==root :
        #print('fin')
        return dist
    elif len(nodes[key].parent)==1:
        return solve(nodes[key].parent[0]-1,nodes,root,-1,dist+1)
    else:
        if start:
            #print('sticks {} nextpoint {} parent{}'.format(sticks,nodes[sticks-1].point,nodes[sticks-1].parent))
            if not nodes[sticks-1].parent:
                return 0
            return solve(nodes[sticks-1].parent[0]-1,nodes,root,-1,dist+1)
        else:
            #print('cant')
            #print(nodes[key])
            return -1

def getroot(nodes,key=1):
    if nodes[key].parent:
        return getroot(nodes,nodes[key].parent[0]-1)
    else:
        return key+1



rootkey=getroot(nodes)

#print('\n\n')
#print('rootkey{}'.format(rootkey))
while keys:
    key=keys.pop()
    #print('kaburi')
    #print(nodes[key])
    maxi=-1
    maxd=-1
    for i in nodes[key].parent:
        #print('i:{}'.format(i))
        ace=solve(key,nodes,rootkey,i,0,True)
        #print('distance {}'.format(ace))
        if maxd<ace:
            maxd=ace
            maxi=i
    nodes[ key ].parent=[maxi]


for i in range(N):
    print(nodes[i].parent[0] if nodes[i].parent else 0)

Submission status: Runtime Error

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

from collections import defaultdict

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

#print(vs)
#print(ws)

L = []

cs = [0] * (1 + N)

def visit(n):
    if cs[n] == 1:
        return
    elif cs[n] == 0:
        cs[n] = 1
        for m in vs[n]:
            visit(m)
        cs[n] = 2
        L.append(n)

for n in range(1, N + 1):
    if cs[n] == 0:
        visit(n)

#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:nrank[x])[0]
    print(r)

Submission status: Runtime Error

Solution code:
from collections import deque

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 remove(self, node):
        Q = deque()
        Q.append(node)
        visited = {}
        while len(Q) > 0:
            v = Q.popleft()
            if v not in self.par:
                continue
            for i in self.par[v]:
                if i in visited:
                    x = visited[i]
                    self.par[x].remove(i)
                visited[i] = v
                Q.append(i)

    def rem(self):
        for node in self.par:
            if len(self.par[node]) > 1:
                self.remove(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 sys
sys.setrecursionlimit(100000000)
N, M = map(int, input().split())
T = {}
D = [0 for _ in range(N+1)]
P = [0 for _ in range(N+1)]
root_id = {i for i in range(1, N+1)}
for _ in range(N+M-1):
    a, b = map(int, input().split())
    if a not in T:
        T[a] = [b]
    else:
        T[a].append(b)
    if b in root_id:
        root_id.remove(b)
root_id = root_id.pop()

def setdep(i, p, d):
    if D[i] == 0:
        D[i] = d
        P[i] = p
    else:
        if D[i] > d:
            T[p].remove(i)
            return None
        else: # D[i] < d:
            T[P[i]].remove(i)
            P[i] = p
    if i not in T:
        return None
    for j in T[i]:
        setdep(j, i, d+1)

setdep(root_id, 0, 1)
for p in P[1:]:
    print(p)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000000000000)
N, M = map(int, input().split())
T = {}
D = [0 for _ in range(N+1)]
P = [0 for _ in range(N+1)]
root_id = {i for i in range(1, N+1)}
for _ in range(N+M-1):
    a, b = map(int, input().split())
    if a not in T:
        T[a] = [b]
    else:
        T[a].append(b)
    if b in root_id:
        root_id.remove(b)
root_id = root_id.pop()

def setdep(i, p, d):
    if D[i] == 0:
        D[i] = d
        P[i] = p
    else:
        if D[i] > d:
            T[p].remove(i)
            return None
        else: # D[i] < d:
            T[P[i]].remove(i)
            P[i] = p
    if i not in T:
        return None
    for j in T[i]:
        setdep(j, i, d+1)

setdep(root_id, 0, 1)
for p in P[1:]:
    print(p)

Submission status: Runtime Error

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,trees):
    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: Runtime Error

Solution code:
	import sys
sys.setrecursionlimit(10000000000000000)
N, M = map(int, input().split())
T = {}
D = [0 for _ in range(N+1)]
P = [0 for _ in range(N+1)]
root_id = {i for i in range(1, N+1)}
for _ in range(N+M-1):
    a, b = map(int, input().split())
    if a not in T:
        T[a] = [b]
    else:
        T[a].append(b)
    if b in root_id:
        root_id.remove(b)
root_id = root_id.pop()

def setdep(i, p, d):
    if D[i] == 0:
        D[i] = d
        P[i] = p
    else:
        if D[i] > d:
            T[p].remove(i)
            return None
        else: # D[i] < d:
            T[P[i]].remove(i)
            P[i] = p
    if i not in T:
        return None
    for j in T[i]:
        setdep(j, i, d+1)

setdep(root_id, 0, 1)
for p in P[1:]:
    print(p)

Submission status: Runtime Error

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

from collections import deque

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

ins = [0]*n
par = [0]*n

# 親をたどるグラフを作る
for _ in range(n-1+m):
    a,b = li_()
    graph[a].append(b)
    ins[b] += 1

# 入次数が尽きたものからスタートに
start = ins.index(0)
que = deque([start])
while que:
    cur = que.popleft()
    for child in graph[cur]:
        ins[child] -= 1
        if ins[child] == 0:
            que.append(child)
            par[child] = cur+1
    
for pi in par:
    print(pi)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
D = defaultdict(lambda: [])
gain = [0]*N
for i in range(N + M - 1):
    a, b = map(int, input().split())
    D[a - 1].append(b - 1)
    gain[b - 1] += 1

ans = [None]*N
def rec(u, p):
    ans[u] = p
    for v in D[u]:
        gain[v] -= 1
    for v in D[u]:
        if gain[v] == 0 and ans[v] is None:
            rec(v, u)

root = gain.index(0)
rec(root, -1)

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

Submission status: Runtime Error

Solution code:
s=input().split()
n,m=int(s[0]),int(s[1])
a=[]
b=[]
isroot=[]
depth=[]
level=[]
decendent=[]
parent=[]
for i in range(n+1):
    isroot.append(1)
    depth.append(-1)
    decendent.append([])
    parent.append([])
    level.append([])
isroot[0]=0
#depth[0]=0
root=0
for i in range(n+m-1):
    s=input().split()
    A,B=int(s[0]),int(s[1])
    a.append(A)
    b.append(B)
    decendent[A].append(B)
    parent[B].append(A)
    isroot[B]=0
for i in range(1,n+1):
    if isroot[i]:
        root=i
        break
depth[root]=0
level[0].append(root)
t=True
for k in range(n+2):
    if t:
        t=False
        for i in level[k]:
                t=True
                for j in decendent[i]:
                    depth[j]=k+1
                    level[k+1].append(j)
                    if level[k].count[j]:
                        level[k].remove(j)
for i in range(1,n+1):
    if root==i:
        print(0)
    else:
        for j in parent[i]:
            if depth[j]==depth[i]-1:
                print(j)
                break

Submission status: Runtime Error

Solution code:
s=input().split()
n,m=int(s[0]),int(s[1])
a=[]
b=[]
isroot=[]
depth=[]
level=[]
decendent=[]
parent=[]
for i in range(n+1):
    isroot.append(1)
    depth.append(-1)
    decendent.append([])
    parent.append([])
    level.append([])
isroot[0]=0
#depth[0]=0
root=0
for i in range(n+m-1):
    s=input().split()
    A,B=int(s[0]),int(s[1])
    a.append(A)
    b.append(B)
    decendent[A].append(B)
    parent[B].append(A)
    isroot[B]=0
for i in range(1,n+1):
    if isroot[i]:
        root=i
        break
depth[root]=0
level[0].append(root)
t=True
for k in range(n+2):
    if t:
        t=False
        for i in level[k]:
                t=True
                for j in decendent[i]:
                    depth[j]=k+1
                    level[k+1].append(j)
                    level[k].remove(j)
for i in range(1,n+1):
    if root==i:
        print(0)
    else:
        for j in parent[i]:
            if depth[j]==depth[i]-1:
                print(j)
                break

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

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]

k = m-1+n
for i in range(k):
    p1,p2 = getMN()
    parents[p2].append(p1)
    childs[p1].append(p2)

dst = [0 for i in range(n+1)]

d = deque()
n_root = 0
for i, x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

def bfs(n_cur):
    for c in childs[n_cur]:
        d.append(c)
        dst[c] = max(dst[c], dst[n_cur]+1)
    while(d):
        bfs(d.pop())

bfs(n_root)

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

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

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]

k = m-1+n
for i in range(k):
    p1,p2 = getMN()
    parents[p2].append(p1)
    childs[p1].append(p2)

dst = [0 for i in range(n+1)]

d = deque()
n_root = 0
for i, x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

def bfs(n_cur):)
    for c in childs[n_cur]:
        d.append(c)
        dst[c] = max(dst[c], dst[n_cur]+1)
    while(d):
        bfs(d.pop())

bfs(n_root)

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

Submission status: Runtime Error

Solution code:
n,m =map(int, input().split())
d=[0]*(10**5)
p=[0]*(10**5)
k = list(range(1,n+1))
for i in range(n+m-1):
    a,b = map(int, input().split())
    if str(b) not in str(d[a]):d[a]=d[a]*10+b
    if str(a) not in str(p[b]):p[b]=p[b]*10+a
    if b in k:k.remove(b)
p[k[0]] = 0
def cal(x,m,pq):
    x = int(x)
    global p
    if len(str(p[x])) <= m:
        p[x] =pq
    if 0 != d[x]:
        for i in range(len(str(d[x]))):
            cal(str(d[x])[i],int(m+1),x)
cal(k[0],1,0)
for i in range(1,n+1):
    print(p[i])

Submission status: Runtime Error

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

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)
t_ln = [0] * (100010)
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: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
L = {}
D = [[0, i] for i in range(N+1)]

for i in range(N + M - 1):
  Data = list(map(int, input().split()))
  if Data[0] in L:
    L[Data[0]].append(Data[1])
  else:
    L[Data[0]] = [Data[1]]
  D[Data[1]][0] += 1

for i in range(1, N+1):
  if D[i][0] == 0:
    s = D[i][1]
    break

P = [[0, 0] for i in range(N + 1)]
S = []
t = L[s]
for i in t:
  S.append([s, i])
  P[i] = [1, s]

cnt = 0
print(P)
while True:
  j = S[cnt][1]
  if j not in L:
    cnt += 1
    continue
  t = L[j]
  for i in t:
    if P[i][0] != 0:
      if P[i][0] < P[j][0] + 1:
        #削除
        L[P[i][1]].remove(i)
        #更新
        P[i] = [P[j][0] + 1, j] 
        M -= 1
      else:
        # 削除
        L[P[j][1]].remove(j)
        M -= 1
  print(P)
  print(L)
  if M == 0:
    break
  cnt += 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)
    if b-1 in root:
        root.remove(b-1)

root = root[0]

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

def find_parent(node):
    node_parent = parent[node]
    if true_parent[node]:
        return true_parent[node]
    elif len(node_parent)==1:
        true_parent[node] = node_parent[0]
        distance[node] = distance[node_parent[0]]+1
        return node_parent[0]
    else:
        mx = 0
        for p in node_parent:
            tmp = find_parent(p)
            if mx < distance[tmp]:
                mx = distance[tmp]
                mxp = p
        true_parent[node] = p
        distance[node] = distance[p]+1
        return p

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

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
import heapq as q

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)
used = [False] * (n+1)

def bfs(p):
    Q = []
    q.heappush(Q, (-1, 0, p))
    while Q:
        depth, p, v = Q.heappop(Q)
        if used[v]:
            continue
        used[v] = True
        D[v] = depth
        P[v] = p
        for t in T[v]:
            q.heappush(Q, (depth - 1, p, t))

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

bfs(root(1))
for p in P[1:]:
    print(p)