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:
# 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(f'\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

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 = {}  # 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
        """
        self.graph[str(t[0])] = self.graph.get(str(t[0]), []).append(t[1])

    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(f'\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

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 = defaultdict(list)  # 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
        """
        self.graph[str(t[0])].append(t[1])

    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(f'\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()
# g.show_graph()

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

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 = defaultdict(list)  # 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: tuple):
        """
        Add edge

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

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

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

        return result

    def visit(self, node: int, visited: list, result: list):
        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(f'\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()
# g.show_graph()

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

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 = defaultdict(list)  # 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: tuple):
        """
        Add edge

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

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

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

        return result

    def visit(self, node: int, visited: list, result: list):
        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(f'\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()
# g.show_graph()

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

Submission status: Runtime Error

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

# n = 6
# m = 3
#
# input_edges = """2 1
# 2 3
# 4 1
# 4 2
# 6 1
# 2 6
# 4 6
# 6 5""".split('\n')
#
# edges = []
# for i in input_edges:
#     st = [int(each) - 1 for each in i.split()]
#     edges.append((st[0], st[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]))


# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)  # 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: tuple):
        """
        Add edge

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

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

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

        return result

    def visit(self, node: int, visited: list, result: list):
        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)

    # # A recursive function used by topologicalSort
    # def topological_sort_util(self, v, visited, stack):
    #
    #     # Mark the current node as visited.
    #     visited[v] = True
    #
    #     # Recur for all the vertices adjacent to this vertex
    #     for i in self.graph[v]:
    #         if visited[i] is False:
    #             self.topological_sort_util(i, visited, stack)
    #             # Push current vertex to stack which stores result
    #             stack.insert(0, v)
    #
    # # The function to do Topological Sort. It uses recursive
    # # topologicalSortUtil()
    # def topological_sort(self) -> list:
    #     # Mark all the vertices as not visited
    #     visited = [False] * self.V
    #     stack = []
    #
    #     # Call the recursive helper function to store Topological
    #     # Sort starting from all vertices one by one
    #     for i in range(self.V):
    #         if visited[i] is False:
    #             self.topological_sort_util(i, visited, stack)
    #     return stack

    def show_graph(self):
        for key in self.graph:
            print(key)
            for value in self.graph[key]:
                print(f'\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()
g.show_graph()

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

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 = defaultdict(list)  # 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: tuple):
        """
        Add edge

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

    # A recursive function used by topologicalSort
    def topological_sort_util(self, v, visited, stack):

        # Mark the current node as visited.
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] is False:
                self.topological_sort_util(i, visited, stack)

            # Push current vertex to stack which stores result
        stack.insert(0, v)

    # The function to do Topological Sort. It uses recursive
    # topologicalSortUtil()
    def topological_sort(self) -> list:
        # Mark all the vertices as not visited
        visited = [False] * self.V
        stack = []

        # Call the recursive helper function to store Topological
        # Sort starting from all vertices one by one
        for i in range(self.V):
            if visited[i] is False:
                self.topological_sort_util(i, visited, stack)
        return stack

    def show_graph(self):
        for key in self.graph:
            print(key)
            for value in self.graph[key]:
                print(f'\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 == len(sorted_nodes) - 1:
        print(0)
    else:
        search_target_nodes = sorted_nodes[node_i_index_in_sorted_nodes + 1:]
        for searching_node in search_target_nodes:
            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
import numpy as np

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

# 根を見つける

nodes = [0 for each in range(n)]

for edge in edges:
    print('edge:', edge)
    nodes[edge[1]] += 1

root_node = np.argmin(edges)


# Class to represent a graph
class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)  # 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: tuple):
        """
        Add edge

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

    # A recursive function used by topologicalSort
    def topological_sort_util(self, v, visited, stack):

        # Mark the current node as visited.
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] is False:
                self.topological_sort_util(i, visited, stack)

            # Push current vertex to stack which stores result
        stack.insert(0, v)

    # The function to do Topological Sort. It uses recursive
    # topologicalSortUtil()
    def topological_sort(self) -> list:
        # Mark all the vertices as not visited
        visited = [False] * self.V
        stack = []

        # Call the recursive helper function to store Topological
        # Sort starting from all vertices one by one
        for i in range(self.V):
            if visited[i] is False:
                self.topological_sort_util(i, visited, stack)

            # Print contents of stack
        print(stack)
        return stack

    def show_graph(self):
        for key in self.graph:
            print(key)
            for value in self.graph[key]:
                print(f'\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()

# This code is contributed by Neelam Yadav

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

up = [[] for _ in range(n)] # [[]]*nした後にappendするのはNG
down = [[] for _ in range(n)]
used = [0]*n # これならOK
res = [0]*n
cnt = 0

for _ in range(n+m-1):
    p, c = map(int, input().split())
    up[c-1].append(p)
    down[p-1].append(c)

for i in range(n):
    if up[i] == []:
        root = i+1
        res[root-1] = 0
        used[root-1] = 1
        cnt += 1
        break

ptank = deque([root])
ctank = deque([root])

def find_c(p):
    for i in down[p-1]:
        if all([used[j-1]==1 for j in up[i-1]]) & (used[i-1]==0):
            res[i-1] = p
            ctank.append(i)

while cnt < n:
    ptank = ctank.copy()
    while len(ctank) != 0:
        used[ctank.popleft()-1] = 1
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    

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

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

import sys
sys.setrecursionlimit(100010)

from collections import defaultdict

vs = defaultdict(set)

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

from functools import lru_cache

@lru_cache(maxsize=None)
def calc(n):
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    return max_distance, max_distance_parent

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

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

import sys
sys.setrecursionlimit(100010)

from collections import defaultdict

vs = defaultdict(set)

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

from functools import lru_cache

@lru_cache(maxsize=N)
def calc(n):
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    return max_distance, max_distance_parent

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

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)

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

cache = {}

def calc(n):
    if n in cache:
        return cache[n]
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    result = max_distance, max_distance_parent
    cache[n] = result
    return result

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

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)

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

from functools import lru_cache

@lru_cache(maxsize=N)
def calc(n):
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    return max_distance, max_distance_parent

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

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(100000000)

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


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

memo = {}
def depth(b):
    if b in memo:
        return memo[b]
    
    res = 0
    for a in BtoA[b]:
        res = max(res, depth(a) + 1)

    memo[b] = res
    return res

for i in range(1, N + 1):
    ans = 0
    for a in BtoA[i]:
        if depth(a) + 1 == depth(i):
            ans = a
            break
    print(ans)

Submission status: Runtime Error

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


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

memo = {}
def depth(b):
    if b in memo:
        return memo[b]
    
    res = 0
    for a in BtoA[b]:
        res = max(res, depth(a) + 1)

    memo[b] = res
    return res

for i in range(1, N + 1):
    ans = 0
    for a in BtoA[i]:
        if depth(a) + 1 == depth(i):
            ans = a
            break
    print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
e=[]
tu=[[] for x in range(n+1)]
d=[0]*(n+1)
fa=[0]*(n+1)
for i in range(n-1+m):
    u,v=map(int,input().split())
    e.append((u,v))
    tu[u].append(v)
    d[v]+=1

def dfs(x):
    if x in vis:
        return
    vis.add(x)
    for t in tu[x]:
        dfs(t)
    tp.append(x)

vis=set()
tp=[]
for i in range(1,n+1):
    if d[i]==0:
      rt=i
      dfs(i)

d=[0]*(n+1);
tp.reverse()
for i in tp:
    for t in tu[i]:
        d[t]=max(d[t],d[i]+1)

for i in e:
    u,v=i
    if d[u]+1==d[v]:
        fa[v]=u

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 全国統一プログラミング王決定戦予選：D - Restore the Tree
back = []


def calc(e):
    global back
    # print 'e =', e, ', b =', back[e]

    if back[e][1] == -1:
        if len(back[e][0]) == 0:
            back[e][1] = 0
            # print 'ret =', 0
            return 0
        elif len(back[e][0]) == 1:
            l = calc(back[e][0][0]) + 1
            back[e][1] = l
            # print 'ret =', l
            return l
        maxl = calc(back[e][0][0])
        maxi = 0
        for i, s in enumerate(back[e][0][1:], 1):
            l = calc(s)
            if l >= maxl:
                maxl = l
                back[e][0][maxi] = -1
                maxi = i
            else:
                back[e][0][i] = -1
        back[e][1] = maxl + 1
        # print 'ret =', maxl + 1
        return maxl + 1
    else:
        # print 'ret =', back[e][1]
        return back[e][1]


def main():
    global back
    N, M = [int(i) for i in raw_input().strip().split(' ')]

    A = []
    for _ in range(N+M-1):
        A.append([int(i)-1 for i in raw_input().strip().split(' ')])
    # H.sort(reverse=False)

    back = [[[], -1] for _ in range(N)]

    for s, e in A:
        back[e][0].append(s)
    # print 'back =', back

    for i, b in enumerate(back):
        if b[1] == -1:
            # back[i][1] = calc(i)
            calc(i)

    # print 'back =', back
    for b in back:
        if b[0] == []:
            print 0
        else:
            for s in b[0]:
                # print 's =', s
                if s != -1:
                    print s+1


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

result = [-2] * N
edge_from = [[] for _ in range(N + 1)]
edge_to = [[] for _ in range(N + 1)]

for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    edge_from[B].append(A)
    edge_to[A].append(B)

parent = []
for i in range(1, N + 1):
    if any(edge_to[i]) and not any(edge_from[i]):
        parent.append(i)
        result[i] = -1
        break

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_

for x in result:
    print(x)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import queue

n, m = map(int, input().split())
p = {i+1:set() for i in range(n)}

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

for c, ps in p.items():

    if len(ps) == 0:
        ps.add(0)
        continue
    elif len(ps) == 1:
        continue

    tp = set(ps)
    for parent in tp:
        ps.remove(parent)

        q = queue.Queue()
        q.put(c)
        visited = set()
        isExist = False
        while not q.empty():
            vq = q.get()
            visited.add(vq)
            if vq == parent:
                isExist = True
                break
            elif vq == 0:
                break
            for ttp in p[vq]:
                if not ttp in visited:
                    q.put(ttp)

        if not isExist:
            ps = set([parent])
            break

for i in range(n):
    print(list(p[i+1])[0])

Submission status: Runtime Error

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