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:
import sys
input = sys.stdin.readline

n,m = map(int, input().split())
G = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    used[b] = 1
root = used.index(0)

dist = [0]*n
def rec(cur, depth):
    dist[cur] = max(dist[cur], depth)
    for to in G[cur]:
        rec(to, depth+1)

rec(root, 0)

par = [0]*n
for from_ in range(n):
    for to in G[from_]:
        if dist[from_] + 1 == dist[to]:
            par[to] = from_+1
print(*par, sep="\n")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(' '))
tree = [[] for i in range(n+1)]
r_tree = [[] for i in range(n+1)]
for i in range(n-1+m):
    a, b = map(int, input().split(' '))
    tree[a].append(b)
    r_tree[b].append(a)
ne = 0
i = 1
while i <= n:
    if len(r_tree[i]) == 0:
        ne = i
        i = n+1
    else:
        i += 1
counter_list = [[] for i in range(n+1)]
def renumber(num,counter):
    if len(tree[num]) == 0:
        return 0
    counter += 1
    for i in tree[num]:
        counter_list[i].append([counter, num])
        renumber(i, counter)
    return 0
counter_list[ne].append([1, 0])
renumber(ne, 1)
for i in range(1, n+1):
    counter_list[i].sort(reverse = True)
    print(counter_list[i][0][1])

Submission status: Runtime Error

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

N, M = map(int, input().split())
check_lst = [False] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] = True
# print (lst)

ans_lst = [[-1, 0] for _ in range(N)] #[親, 距離]を要素とするリスト
#根を求める = どこからも辺が伸びていないところ --> check_lst = Falseの場所
n = check_lst.index(False)
ans_lst[n][0] = -1
# print (n)

def dfs(i): #iからの経路を探す
    distance = ans_lst[i][1]
    for j in lst[i]:
        # print (j)
        if distance + 1 > ans_lst[j][1]:#距離が最長となるとき
            ans_lst[j][0] = i
            ans_lst[j][1] = distance + 1
            dfs(j)
    return 

dfs(n)
# print (ans_lst)

# print ('以下答え')
for i, d in ans_lst:
    print (i + 1)

Submission status: Runtime Error

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

L=[[]for i in range(N+1)]
p=[0 for i in range(N+1)]

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

for i in range(1,N+1):
    if p[i]==0:
        P=i
#print(P)
p[P]=[0,0]
A=[]
for i in L[P]:
    A.append([i,P,1])
for i in range(10**6):
    if i==len(A):
        break
    else:
        p[A[i][0]]=[A[i][1],A[i][2]]
        for j in L[A[i][0]]:
            A.append([j,A[i][0],A[i][2]+1])
    #print(p)
    #print(A)
for i in range(1,N+1):
    print(p[i][0])

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)


# 入力
N, M = map(int, input().split())
A, B = zip(*(map(int, input().split()) for _ in range(N - 1 + M)))

# 各頂点の深さを求め、深さを利用して元の木を復元する
G = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G[b].add(a)


@lru_cache(maxsize=None)
def f(v):
    return 1 + max((f(p) for p in G[v]), default=0)


ans = '\n'.join(
    str(max(G[i], key=f, default=0))
    for i in range(1, N + 1)
)

# 出力
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

# 入力
N, M = map(int, input().split())
A, B = zip(*(map(int, input().split()) for _ in range(N - 1 + M)))

# 各頂点の深さを求め、深さを利用して元の木を復元する
G = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G[b].add(a)


@lru_cache(maxsize=None)
def f(v):
    return 1 + max((f(p) for p in G[v]), default=0)


ans = '\n'.join(
    str(max(G[i], key=f, default=0))
    for i in range(1, N + 1)
)

# 出力
print(ans)

Submission status: Runtime Error

Solution code:
#include <math.h>
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <iostream>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;


int main()
{
    int N, M;
    cin >> N >> M;
    map<int, set<pair<int, int>>> OUT;
    map<int, set<int>> IN;
    set<int> start;
    FOR (i,0,N){
        start.insert(i);
    }
    FOR(i,0,N+M-1){
        int a, b;
        cin >> a >> b;
        start.erase(b - 1);
        OUT[a - 1].insert(make_pair(i, b - 1));
        IN[b - 1].insert(i);
    }
    vector<int> P(N, 0);
    while (start.size()>0){
        int now = *start.begin();
        start.erase(now);
        for (auto x:OUT[now]){
            int b = x.first;
            int nex = x.second;
            IN[nex].erase(b);
            if (IN[nex].size()==0){
                start.insert(nex);
                P[nex] = now + 1;
            }
        }
    }
    FOR(i,0,N){
        cout << P[i] << endl;
    }
}

Submission status: Runtime Error

Solution code:
\import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        IN[nex].remove(b)
        if not IN[nex]:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    par = [[] for _ in range(N)]
    chi = [[] for _ in range(N)]
    root = None
    for i in range(N + M - 1):
        chi[A[i] - 1].append(B[i] - 1)
        par[B[i] - 1].append(A[i] - 1)

    #print(chi)
    #print(par)
    for i in range(N):
        if len(par[i]) < 1:
            root = i
            par[i].append(-1)
            break

    depths = [0] * (N)
    def dfs(i, d):
        depths[i] = max(depths[i], d)
        for ch in chi[i]:
            dfs(ch, d + 1)
    dfs(root, 0)
    #print(depths)

    for i in range(N):
        if len(par[i]) > 1:
            for p in par[i]:
                if depths[p] == depths[i] - 1:
                    ret = p
        else:
            ret = par[i][0]
        print(ret + 1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N-1+M)  # type: "List[int]" 
    B = [int()] * (N-1+M)  # type: "List[int]" 
    for i in range(N-1+M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def dfs(graph, nd, toprogy, is_visited):
    is_visited.add(nd)
    for adj in graph[nd]:
        if adj not in is_visited:
            dfs(graph, adj, toprogy, is_visited)

    toprogy.appendleft(nd)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    inv_graph = {}
    for i in range(1, N + 1):
        graph[i] = []
        inv_graph[i] = []

    for i in range(N - 1 + M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)
        inv_graph[b].append(a)

    sys.setrecursionlimit(20000)
    toprogy = deque([])
    is_visited = set([])
    for i in range(1, N + 1):
        if i not in is_visited:
            dfs(graph, i, toprogy, is_visited)

    toprogical_order = {}
    for i in range(N):
        toprogical_order[toprogy[i]] = i + 1

    for i in range(1, N + 1):
        max_toprogy = 0
        true_parent = 0
        for pare in inv_graph[i]:
            if max_toprogy < toprogical_order[pare]:
                max_toprogy =toprogical_order[pare]
                true_parent = pare
        print true_parent

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def dfs(graph, nd, toprogy, is_visited):
    is_visited.add(nd)
    for adj in graph[nd]:
        if adj not in is_visited:
            dfs(graph, adj, toprogy, is_visited)

    toprogy.appendleft(nd)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    inv_graph = {}
    for i in range(1, N + 1):
        graph[i] = []
        inv_graph[i] = []

    for i in range(N - 1 + M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)
        inv_graph[b].append(a)


    toprogy = deque([])
    is_visited = set([])
    for i in range(1, N + 1):
        if i not in is_visited:
            dfs(graph, i, toprogy, is_visited)

    toprogical_order = {}
    for i in range(N):
        toprogical_order[toprogy[i]] = i + 1

    for i in range(1, N + 1):
        max_toprogy = 0
        true_parent = 0
        for pare in inv_graph[i]:
            if max_toprogy < toprogical_order[pare]:
                max_toprogy =toprogical_order[pare]
                true_parent = pare
        print true_parent

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


def get_root() -> int:
    result_ = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result_[dist] = True
    return result_.index(False)


def get_child(graph, parents, depth):
    childs = set()
    next_ = False
    for parent in parents:
        for child in graph.get(str(parent), []):
            childs.add(child)
            result_list[child] = parent + 1
            next_ = True
    # print('parents', parents)
    # print('childs', childs)
    if next_ is True:
        # if childs is not None:
        get_child(graph, childs, depth + 1)


i = [int(each) for each in input().split()]
n, m = i[0], i[1]

# グラフ作成
g = dict()
edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    add_edge((st[0], st[1]))

# 深さ探索

# 根を探索
root_node = get_root()  # type: int

current_node = root_node

result_list = [None for i in range(n)]
result_list[root_node] = 0

get_child(g, {root_node}, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


def get_root() -> int:
    result_ = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result_[dist] = True
    return result_.index(False)


def get_child(graph, parents, depth):
    childs = set()
    next = False
    for parent in parents:
        for child in graph.get(str(parent), []):
            childs.add(child)
            result_list[child] = parent + 1
            next = True
    print('parents', parents)
    print('childs', childs)
    if next is True:
        # if childs is not None:
        get_child(graph, childs, depth + 1)


i = [int(each) for each in input().split()]
n, m = i[0], i[1]

# グラフ作成
g = dict()
edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    add_edge((st[0], st[1]))

# 深さ探索

# 根を探索
root_node = get_root()

current_node = root_node

# visited = [False] * n
# visited[root] = True
result_list = [None] * n
result_list[root_node] = 0
# max_depth_list = [None] * n
# max_depth_list[root] = 0

get_child(g, {root_node}, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


def get_root() -> int:
    result = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result[dist] = True
    for i, each in enumerate(result):
        if each is False:
            return i
    raise Exception


def get_child(graph, parent, depth):
    # print('parent', parent, 'childs', graph.get(str(parent), []))
    for child in graph.get(str(parent), []):
        get_child(graph, child, depth + 1)
        if depth_list[child] < depth:
            depth_list[child] = depth
            result_list[child] = parent + 1


i = [int(each) for each in input().split()]
n, m = i[0], i[1]

# グラフ作成
g = dict()
edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    add_edge((st[0], st[1]))

# 深さ探索

# 根を探索
root = get_root()

current_node = root

# visited = [False] * n
# visited[root] = True
result_list = [None] * n
result_list[root] = 0
depth_list = [-1] * n
depth_list[root] = 0

get_child(g, root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


def get_root() -> int:
    result = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result[dist] = True
    for i, each in enumerate(result):
        if each is False:
            return i
    raise Exception


def get_child(graph, parent, depth):
    # print('parent', parent, 'childs', graph.get(str(parent), []))
    for child in graph.get(str(parent), []):
        get_child(graph, child, depth + 1)
        if visited[child] is False:
            visited[child] = True
            result_list[child] = parent + 1


i = [int(each) for each in input().split()]
n, m = i[0], i[1]

# グラフ作成
g = dict()
edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    add_edge((st[0], st[1]))

# 深さ探索

# 根を探索
root = get_root()

current_node = root

visited = [False] * n
result_list = [None] * n
result_list[root] = 0
depth_list = [-1] * n
depth_list[root] = 0

get_child(g, root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


def get_root() -> int:
    result = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result[dist] = True
    for i, each in enumerate(result):
        if each is False:
            return i
    raise Exception


def get_child(parent, depth):
    childs = g.get(str(parent), [])

    for child in childs:
        get_child(parent, depth + 1)
        if visited is False:
            visited[child] = True
            result_list[child] = parent + 1


i = [int(each) for each in input().split()]
n, m = i[0], i[1]

g = dict()
edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    add_edge((st[0], st[1]))

# 深さ探索

# 根を探索
root = get_root()

current_node = root

visited = [False] * n
result_list = [None] * n
result_list[root] = 0
depth_list = [-1] * n
depth_list[root] = 0

get_child(root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


def get_root() -> int:
    result = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result[dist] = True
    for i, each in enumerate(result):
        if each is False:
            return i
    raise Exception


def get_child(parent, depth):
    childs = g.get(str(parent), [])

    for child in childs:
        if depth_list[child] < depth:
            depth_list[child] = depth
            result_list[child] = parent + 1
        get_child(child, depth + 1)


i = [int(each) for each in input().split()]
n, m = i[0], i[1]

edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    edges.append((st[0], st[1]))

g = dict()

for edge in edges:
    add_edge(edge)

# 深さ探索

# 根を探索
root = get_root()

current_node = root

visited = [False] * n
result_list = [None] * n
result_list[root] = 0
depth_list = [-1] * n
depth_list[root] = 0

get_child(root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
i = [int(each) for each in input().split()]
n, m = i[0], i[1]

edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    edges.append((st[0], st[1]))

g = dict()


def add_edge(t):
    a = g.get(str(t[0]), [])
    a.append(t[1])
    g[str(t[0])] = a


for edge in edges:
    g.add_edge(edge)


def get_root() -> int:
    result = [False] * n
    for node in range(n):
        for dist in g.get(str(node), []):
            result[dist] = True
    for i, each in enumerate(result):
        if each is False:
            return i
    raise Exception


# 深さ探索

# 根を探索
root = get_root()

current_node = root

visited = [False] * n
result_list = [None] * n  # type: List[int]
result_list[root] = 0
depth_list = [-1] * n  # type: List[int]
depth_list[root] = 0


def get_child(parent, depth):
    childs = g.get(str(parent), [])

    for child in childs:
        if depth_list[child] < depth:
            depth_list[child] = depth
            result_list[child] = parent + 1
        get_child(child, depth + 1)


get_child(root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
# Python program to print topological sorting of a DAG
# from collections import defaultdict

i = [int(each) for each in input().split()]
n, m = i[0], i[1]

edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    edges.append((st[0], st[1]))


# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = dict()  # dictionary containing adjacency List
        self.V = vertices  # No. of vertices

    # # function to add an edge to graph
    # def add_edge(self, u: int, v: int):
    #     """
    #     Add edge
    #
    #     :param u: parent
    #     :param v: child
    #     :return:  None
    #     """
    #     self.graph[str(u)].append(v)

    # function to add an edge to graph
    def add_edge(self, t):
        """
        Add edge

        :param t: edge()
        :return: None
        """
        a = self.graph.get(str(t[0]), [])
        a.append(t[1])
        self.graph[str(t[0])] = a

    def topological_sort(self):
        result = []
        visited = [False] * self.V

        for node in range(self.V):
            self.visit(node, visited, result)
        return result

    def visit(self, node, visited, result):
        if not visited[node]:
            visited[node] = True
            for out_node in self.graph.get(str(node), []):
                self.visit(out_node, visited, result)
            result.insert(0, node)

    def show_graph(self):
        for key in range(self.V):
            print('key', key)
            for value in self.graph.get(str(key), []):
                print('\t -> ', value)

    def is_parent(self, parent, child):
        return child in self.graph.get(str(parent), [])

    def get_root(self) -> int:
        result = [False] * self.V
        for node in range(self.V):
            for dist in self.graph.get(str(node), []):
                result[dist] = True
        for i, each in enumerate(result):
            if each is False:
                return i
        raise Exception


g = Graph(n)
for edge in edges:
    g.add_edge(edge)

# sorted_nodes = g.topological_sort()
# g.show_graph()

# for i in range(n):
#     node_i_index_in_sorted_nodes = sorted_nodes.index(i)
#     if node_i_index_in_sorted_nodes == 0:
#         print(0)
#     else:
#         search_target_nodes = sorted_nodes[:node_i_index_in_sorted_nodes]
#         search_target_nodes.reverse()
#         for searching_node in search_target_nodes:
#             if g.is_parent(searching_node, i):
#                 print(searching_node + 1)
#                 break

# 深さ探索

# 根を探索
root = g.get_root()  # type: int

current_node = root

visited = [False] * n
result_list = [None] * n  # type: List[int]
result_list[root] = 0
depth_list = [-1] * n  # type: List[int]
depth_list[root] = 0


def get_child(parent, depth):
    childs = g.graph.get(str(parent), [])

    for child in childs:
        if depth_list[child] < depth:
            depth_list[child] = depth
            result_list[child] = parent + 1
        get_child(child, depth + 1)

get_child(root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
# Python program to print topological sorting of a DAG
# from collections import defaultdict

i = [int(each) for each in input().split()]
n, m = i[0], i[1]

edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    edges.append((st[0], st[1]))


# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = dict()  # dictionary containing adjacency List
        self.V = vertices  # No. of vertices

    # # function to add an edge to graph
    # def add_edge(self, u: int, v: int):
    #     """
    #     Add edge
    #
    #     :param u: parent
    #     :param v: child
    #     :return:  None
    #     """
    #     self.graph[str(u)].append(v)

    # function to add an edge to graph
    def add_edge(self, t):
        """
        Add edge

        :param t: edge()
        :return: None
        """
        a = self.graph.get(str(t[0]), [])
        a.append(t[1])
        self.graph[str(t[0])] = a

    def topological_sort(self):
        result = []
        visited = [False] * self.V

        for node in range(self.V):
            self.visit(node, visited, result)
        return result

    def visit(self, node, visited, result):
        if not visited[node]:
            visited[node] = True
            for out_node in self.graph.get(str(node), []):
                self.visit(out_node, visited, result)
            result.insert(0, node)

    def show_graph(self):
        for key in range(self.V):
            print('key', key)
            for value in self.graph.get(str(key), []):
                print('\t -> ', value)

    def is_parent(self, parent, child):
        return child in self.graph.get(str(parent), [])

    def get_root(self) -> int:
        result = [False] * self.V
        for node in range(self.V):
            for dist in self.graph.get(str(node), []):
                result[dist] = True
        for i, each in enumerate(result):
            if each is False:
                return i
        raise Exception


g = Graph(n)
for edge in edges:
    g.add_edge(edge)

# sorted_nodes = g.topological_sort()
# g.show_graph()

# for i in range(n):
#     node_i_index_in_sorted_nodes = sorted_nodes.index(i)
#     if node_i_index_in_sorted_nodes == 0:
#         print(0)
#     else:
#         search_target_nodes = sorted_nodes[:node_i_index_in_sorted_nodes]
#         search_target_nodes.reverse()
#         for searching_node in search_target_nodes:
#             if g.is_parent(searching_node, i):
#                 print(searching_node + 1)
#                 break

# 深さ探索

# 根を探索
import numpy as np
root = g.get_root()  # type: int

current_node = root

visited = [False] * n
result_list = [None] * n  # type: List[int]
result_list[root] = 0
depth_list = [np.inf] * n  # type: List[int]
depth_list[root] = 0


def get_child(parent, depth):
    childs = g.graph.get(str(parent), [])

    for child in childs:
        if depth_list[child] > depth:
            depth_list[child] = depth
            result_list[child] = parent + 1

        get_child(child, depth + 1)


get_child(root, 0)
for result in result_list:
    print(result)

Submission status: Runtime Error

Solution code:
# Python program to print topological sorting of a DAG
# from collections import defaultdict

i = [int(each) for each in input().split()]
n, m = i[0], i[1]

edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    edges.append((st[0], st[1]))


# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = dict()  # dictionary containing adjacency List
        self.V = vertices  # No. of vertices

    # # function to add an edge to graph
    # def add_edge(self, u: int, v: int):
    #     """
    #     Add edge
    #
    #     :param u: parent
    #     :param v: child
    #     :return:  None
    #     """
    #     self.graph[str(u)].append(v)

    # function to add an edge to graph
    def add_edge(self, t):
        """
        Add edge

        :param t: edge()
        :return: None
        """
        a = self.graph.get(str(t[0]), [])
        a.append(t[1])
        self.graph[str(t[0])] = a

    def topological_sort(self):
        result = []
        visited = [False] * self.V

        for node in range(self.V):
            self.visit(node, visited, result)
        return result

    def visit(self, node, visited, result):
        if not visited[node]:
            visited[node] = True
            for out_node in self.graph.get(str(node), []):
                self.visit(out_node, visited, result)
            result.insert(0, node)

    def show_graph(self):
        for key in range(self.V):
            print('key', key)
            for value in self.graph.get(str(key), []):
                print('\t -> ', value)

    def is_parent(self, parent, child):
        return child in self.graph.get(str(parent), [])


g = Graph(n)
for edge in edges:
    g.add_edge(edge)

sorted_nodes = g.topological_sort()
# print(sorted_nodes)
g.show_graph()

result = []
for i in range(n):
    # print('-----Node', i, '-----')
    node_i_index_in_sorted_nodes = sorted_nodes.index(i)
    if node_i_index_in_sorted_nodes == 0:
        print(0)
    else:
        search_target_nodes = sorted_nodes[:node_i_index_in_sorted_nodes]
        search_target_nodes.reverse()
        # print('search_target_nodes', search_target_nodes)
        for searching_node in search_target_nodes:
            # print('searching_node', searching_node)
            if g.is_parent(searching_node, i):
                print(searching_node + 1)
                break

Submission status: Runtime Error

Solution code:
# Python program to print topological sorting of a DAG
# from collections import defaultdict

i = [int(each) for each in input().split()]
n, m = i[0], i[1]

edges = []
for i in range(n - 1 + m):
    st = [int(each) - 1 for each in input().split()]
    edges.append((st[0], st[1]))


# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = dict()  # dictionary containing adjacency List
        self.V = vertices  # No. of vertices

    # function to add an edge to graph
    # def add_edge(self, u: int, v: int):
    #     """
    #     Add edge
    #
    #     :param u: parent
    #     :param v: child
    #     :return:  None
    #     """
    #     self.graph[str(u)].append(v)

    def add_edge(self, t):
        """
        Add edge

        :param t: edge()
        :return: None
        """
        a = self.graph.get(str(t[0]), [])
        a.append(t[1])
        self.graph[str(t[0])] = a

    def topological_sort(self):
        result = []
        visited = [False] * self.V

        for node in range(self.V):
            self.visit(node, visited, result)
        return result

    def visit(self, node, visited, result):
        if not visited[node]:
            visited[node] = True
            for out_node in self.graph.get(str(node), []):
                self.visit(out_node, visited, result)
            result.insert(0, node)

    def show_graph(self):
        for key in self.graph:
            print(key)
            for value in self.graph[key]:
                print('\t -> {value}')

    def is_parent(self, parent, child):
        return child in self.graph.get(str(parent), [])


g = Graph(n)
for edge in edges:
    g.add_edge(edge)

sorted_nodes = g.topological_sort()

result = []
for i in range(n):
    node_i_index_in_sorted_nodes = sorted_nodes.index(i)
    if node_i_index_in_sorted_nodes == 0:
        print(0)
    else:
        search_target_nodes = sorted_nodes[:node_i_index_in_sorted_nodes]
        search_target_nodes.reverse()
        # print('search_target_nodes', search_target_nodes)
        for searching_node in search_target_nodes:
            # print('searching_node', searching_node)
            if g.is_parent(searching_node, i):
                print(searching_node + 1)
                break