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())
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:
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):
    #print(([v.dst for v in vtxs]))
    #c is pure integer
    #print("n_cur = {}".format(n_cur))
    for c in childs[n_cur]:
        d.append(c)
        #print("c = {}".format(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:
import sys
sys.setrecursionlimit(1000000)
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)
        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 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())

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

root = 0
for i in range(N + M - 1):
  if P[i] == 0:
    root = i
    break

found = {}
found[root] = 0
added = set()
added.add(root)

def d(node):
  for c in E[node]:
    if c not in added:
      added.add(c)
      # found.append((node, c))
      found[c] = node + 1
      d(c)
    
d(root)

for c in range(N):
  print(found[c])

Submission status: Runtime Error

Solution code:
import numpy as np

class Tree(object):
    def __init__(self, edges, m):
        self.par = {}
        self.fix_d = {}
        self.m = m
        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
        d = None
        p = None
        for v in self.par[node]:
            dep = self.depth(v) + 1
            if p == None:
                d = dep
                p = v
            elif d == dep:
                p = None
                d = None
                self.m -= 2
            elif dep > d:
                d = dep
                p = v
                self.m -= 1
            if self.m == 0:
                break
        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 and self.m != 0:
                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, m)
t.rem()
for i in range(1, n + 1):
    print(t.parent(i))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50000000)

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

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

dfs(first, 1, [])
anslist = [0 for i in range(N+1)]
for i in range(1, N+1):
    if len(pathlist[i]) != 0:
        anslist[i] = pathlist[i][-1]
        anslist[pathlist[i][-1]] = pathlist[i][-2]
for i in range(1, N+1):
    print(anslist[i])

Submission status: Runtime Error

Solution code:
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)
        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(500000)

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

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

dfs(first, 1, [])
anslist = [0 for i in range(N+1)]
for i in range(1, N+1):
    if len(pathlist[i]) != 0:
        anslist[i] = pathlist[i][-1]
        anslist[pathlist[i][-1]] = pathlist[i][-2]
for i in range(1, N+1):
    print(anslist[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:
import numpy as np
N,M = map(int,input().split())
AB = []
for i in range(N+M-1):
    AB.append(list(map(int,input().split())))
npAB = np.array(AB)
# 1をひく
anstree = [0]*N
bcount = (npAB[:,1]==np.arange(1,N+1)[:,np.newaxis]).sum(axis=1)
root = np.arange(1,N+1)[bcount==0]
nowlayer = [root]
nextlayer = []
count = 1
while(count < N):
    nextlayer=np.arange(1,N+1)[bcount==1]
    for node in nextlayer:
        anstree[node-1] = npAB[np.where(npAB[:,1]==node)[0][0]][0]
        count += 1
    for lay in nowlayer:
        npAB = npAB[npAB[:,0]!=lay]
    nowlayer = nextlayer
    bcount = (npAB[:,1]==np.arange(1,N+1)[:,np.newaxis]).sum(axis=1)
for node in anstree:
    print(node)

Submission status: Runtime Error

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

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

dfs(first, 1, [])
anslist = [0 for i in range(N+1)]
for i in range(1, N+1):
    if len(pathlist[i]) != 0:
        anslist[i] = pathlist[i][-1]
        for j in range(1, len(pathlist[i])):
            anslist[pathlist[i][-j]] = pathlist[i][-j-1]
for i in range(1, N+1):
    print(anslist[i])

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], False
        if node not in self.par:
            self.fix_d[node] = 0
            return 0, False
        br = len(self.par[node]) > 1
        d = None
        p = None
        for v in self.par[node]:
            dep, branched = self.depth(v)
            dep += 1
            if branched:
                d = dep
                p = v
                br = True
                break
            elif p == None:
                d = dep
                p = v
            elif d == dep:
                p = None
                d = None
            elif dep > d:
                d = dep
                p = v
        self.par[node] = [p]
        self.fix_d[node] = d
        return d, br

    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:
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)]

k = m-1+n
for i in range(k):
    p1,p2 = getMN()
    parents[p2].append(p1)
    childs[p1].append(p2)
#vtxs = [vertex() for i in range(n+2)]
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):
    #print(([v.dst for v in vtxs]))
    #c is pure integer
    #print("n_cur = {}".format(n_cur))
    for c in childs[n_cur]:
        d.append(c)
        #print("c = {}".format(c))
        dst[c] = max(dst[c], dst[n_cur]+1)
    #print("d = {}".format(d))
    while(d):
        bfs(d.popleft())


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:
import sys

sys.setrecursionlimit(20000)

def dfs(temp):
    global dist, e, count_from, 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:
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        b = []
        for j in range(le):
            if not i == j:
                b.append(l[j])

        ans = anscestor(a, parent)
        if all(k in ans for k in b):
            return [a]


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

parent = [[] 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, n in enumerate(parent):
    if len(n) >= 2:
        parent[i] = check(n, 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:
import copy
n, m = map(int, input().split())
reverse_path_dict = {}
for i in range(n):
  reverse_path_dict[i+1] = []
for i in range(n+m-1):
  f, t = map(int, input().split())
  reverse_path_dict[t].append(f)

def rec_get_max_path(path_list=[]):
  current_node = path_list[-1]
  path_cand = reverse_path_dict[current_node]
  if len(path_cand) == 0:
    return path_list
  res_path_list = []
  for c in path_cand:
    tmp_path_list = copy.deepcopy(path_list)
    tmp_path_list.append(c)
    tmp_res_path_list = rec_get_max_path(tmp_path_list)
    if len(tmp_res_path_list) > len(res_path_list):
      res_path_list = tmp_res_path_list
  return res_path_list

for i in range(n):
  path_cand = reverse_path_dict[i+1]
  if len(path_cand) == 0:
    print(0)
  elif len(path_cand) == 1:
    print(path_cand[0])
  else:
    res_path_list = rec_get_max_path([i+1])
    print(res_path_list[1])
    for j in range(len(res_path_list)-1):
      reverse_path_dict[res_path_list[j]] = [res_path_list[j+1]]

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(x):
    for pe in par[x]:
        if used[pe]==0:
            return False
    return True
#xの下のusedとresを埋める
def f(x):
    for e in op[x]:
        if used[e]==0 and g(e):
            used[e]=1
            res[e]=x+1
            f(e)
f(x)
for i in range(n):
    print(res[i])

Submission status: Runtime Error

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

z = [0]*N
for a, b in AB:
    z[b] += 1

ans = [-1]*N
root = z.index(0)
ok = [False]*N
def rec(u, p):
    ans[u] = p
    ok[u] = True
    for v in D[u]:
        z[v] -= 1
    for v in D[u]:
        if z[v] == 0 and not ok[v]:
            rec(v, u)


rec(root, -1)

for i in range(N):
    print(ans[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)]

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


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

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

bfs(n_root)



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

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 temp < 0:
        return 0

    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 networkx as nx

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
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, dep):
    global ans
    global dist
    if dist[s] < dep:
        return
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t, dep + 1)


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

for x in ans:
    print(x)

Submission status: Runtime Error

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

parents = [-1] * N
v0s = [set() for v in range(N)] # 前回まで
vRoot = [v for v in range(N) if indegs[v] == 0][0]

vNows = set([vRoot])
while vNows:
    vNexts = set()
    v0News = [set() for v in range(N)] # 今回新しく
    for vNow in vNows:
        for v2 in adjL[vNow]:
            parents[v2] = vNow
            vNexts.add(v2)
            v0News[v2].add(vNow)
    vNows = vNexts

    for v in range(N):
        if not v0News[v]: continue
        for v0 in v0s[v]:
            adjL[v0].remove(v)
    for v in range(N):
        v0s[v] = v0News[v]

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

Submission status: Runtime Error

Solution code:
from collections import deque

def topological_sort(V, to):
    cnt = [0]*V
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = deque(i for i in range(V) if cnt[i]==0)
    res = []
    while len(Q) > 0:
        i = Q.popleft()
        res.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 = s[j][1]
            I = j
    print(I+1)

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 = [-1] * (N + 1)
P = [0] * (N + 1)


def dfs(p, d):
    for c in G[p]:
        if D[c] < d + 1:
            D[c] = d + 1
            P[c] = p
            dfs(c, d + 1)


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

Submission status: Runtime Error

Solution code:
def is_child(graph, start, goal):
    if start not in graph:
        return False
    if goal in graph[start]:
        return True
    for s in graph[start]:
        if is_child(graph, s, goal):
            return True
    return False


def main():
    n, m = map(int, raw_input().split())
    graph = {}
    end = {}
    for _ in xrange(n - 1 + m):
        s, e = map(int, raw_input().split())
        if s not in graph:
            graph[s] = set()
        if e not in end:
            end[e] = []
        graph[s].add(e)
        end[e].append(s)
    
    for e, ss in end.items():
        if len(ss) <= 1:
            continue
        for s in ss:
            graph[s].remove(e)
        for s1 in ss:
            graph[s1].add(e)
            if any(s1 != s2 and not is_child(graph, s2, e) for s2 in ss):
                graph[s1].remove(e)
            else:
                break
    tree = [0] * n
    for s, ee in graph.items():
        for e in ee:
            tree[e - 1] = s
    for t in tree:
        print t


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import networkx as nx
import numpy as np

G = nx.DiGraph()

n, m = (int(i) for i in input().split())  

G.add_nodes_from(np.arange(n))

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

G.add_edges_from(e)
G_copy = G.copy()

for u, v in G.edges():
    G_copy.remove_edge(u, v)
    if (not(nx.has_path(G_copy, u, v))):
        G_copy.add_edge(u, v)

e_list = np.zeros(n)
for u, v in G_copy.edges():
    e_list[v-1] = u
    
for u in e_list:
    print(int(u))

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=[int(i) for i in input().split(" ")]
 
G=np.zeros((N,N),dtype=np.int)
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:
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)]
dst = [0 for i in range(n+2)]
d = deque()
for i ,x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

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

bfs(n_root)


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

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
        d = None
        p = None
        for v in self.par[node]:
            dep = self.depth(v) + 1
            if p == None:
                d = dep
                p = v
            elif d == dep:
                p = None
                d = None
            elif dep > d:
                d = dep
                p = v
        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:
def add_children(graph, children, start):
    children[start - 1] = children[start - 1].union(graph[start])
    for s in graph[start]:
        if s not in graph:
            continue
        children[start - 1] = children[start - 1].union(add_children(graph, children, s))
    return children[start - 1]


def main():
    n, m = map(int, raw_input().split())
    graph = {}
    end = {}
    for _ in xrange(n - 1 + m):
        s, e = map(int, raw_input().split())
        if s not in graph:
            graph[s] = set()
        if e not in end:
            end[e] = []
        graph[s].add(e)
        end[e].append(s)
    children = [set() for _ in xrange(n)]
    for s in graph:
        add_children(graph, children, s)
    for e, ss in end.items():
        if len(ss) <= 1:
            continue
        for s in ss:
            graph[s].remove(e)
        for s1 in ss:
            graph[s1].add(e)
            if any(s1 != s2 and e not in children[s2-1] for s2 in ss):
                graph[s1].remove(e)
            else:
                break
    tree = [0] * n
    for s, ee in graph.items():
        for e in ee:
            tree[e - 1] = s
    for t in tree:
        print t


if __name__ == '__main__':
    main()