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

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

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

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

def dfs(p, i, depth):
    if used[i]:
        return None
    D[i] = depth
    P[i] = p
    used[i] = True
    for t in tuple(T[i]):
        RT[t].remove(i)
    for t in tuple(T[i]):
        if not RT[t]:
            dfs(i, t, depth+1)

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

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

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

import sys
sys.setrecursionlimit(200000)

from collections import defaultdict

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

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




L = []

cs = [0] * (1 + N)

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

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



nrank = {}

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



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

Solution (Python):
from collections import deque, defaultdict


def main():
    N, M = map(int, input().split())
    childs = defaultdict(list)
    parents = defaultdict(int)
    for i in range(N+M-1):
        a, b = map(int, input().split())
        childs[a].append(b)
        parents[b] += 1
    q = deque(x for x in range(1, N+1) if parents[x] == 0)
    ans = defaultdict(int)
    while(len(q)):
        n = q.popleft()
        for c in childs[n]:
            parents[c] -= 1
            if parents[c] == 0:
                q.append(c)
                ans[c] = n
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict,deque
v,n=map(int,input().split())
n+=v-1
es=[[int(x)for x in input().split()]for _ in range(n)]
outs=defaultdict(list)
ins=defaultdict(int)
for v1,v2 in es:
    outs[v1].append(v2)
    ins[v2]+=1
q=deque(v1 for v1 in range(v)if ins[v1]==0)
res=[]
f=[0]*(v+1)
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
            f[v2]=v1
for t in f[1:]:print(t)

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

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

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

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

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

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

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

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

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

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

Solution (Python):

from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007


"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""


"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""


"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""


import queue
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
for a,b in c:
    v[a].append(b)
    ins[b] += 1
ans = [-1 for i in range(n)]
q = queue.Queue()
for i in range(n):
    if ins[i] == 0:
        q.put(i)
while not q.empty():
    i = q.get()
    for j in v[i]:
        ans[j] = i
        ins[j] -= 1
        if ins[j] == 0:
            q.put(j)
for i in ans:
    print(i+1)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

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

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


for _ in range(n-1+m):
    a,b = li_()
    graph[a].append(b)
    ins[b] += 1


start = ins.index(0)
que = deque([start])
while que:
    cur = que.popleft()
    for child in graph[cur]:
        ins[child] -= 1
        if ins[child] == 0:
            que.append(child)
            par[child] = cur+1
    
for pi in par:
    print(pi)

Solution (Python):

from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007


"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""


"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""


"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""


import queue
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
for a,b in c:
    v[a].append(b)
    ins[b] += 1
ans = [-1 for i in range(n)]
q = queue.Queue()
for i in range(n):
    if ins[i] == 0:
        q.put(i)
while not q.empty():
    i = q.get()
    for j in v[i]:
        ans[j] = i
        ins[j] -= 1
        if ins[j] == 0:
            q.put(j)
for i in ans:
    print(i+1)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def main():
    n, m = get_int_list()
    A = []
    B = []
    for _ in range(n - 1 + m):
        a, b = get_int_list()
        A.append(a)
        B.append(b)

    root = (set(A) - set(B)).pop()
    graph = defaultdict(list)
    for a, b in zip(A, B):
        graph[a].append(b)
    known = {root}
    deq = deque([root])
    added = Counter()
    cnt = 0
    while cnt < n - 1 + m:
        parent = deq.popleft()
        children = graph[parent]
        for c in children:
            cnt += 1
            if c in known:
                added[c] += 1
                continue
            known.add(c)
            deq.append(c)
    parents = [0] * n
    deq = deque([root])
    cnt = 1
    while cnt < n:
        parent = deq.popleft()
        children = graph[parent]
        for c in children:
            if added[c] > 0:
                added[c] -= 1
                continue
            parents[c-1] = parent
            cnt += 1
            deq.append(c)
    for parent in parents:
        print(parent)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)


n, m = map(int, input().split())
depth = [0 for _ in range(n)]
chil = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]

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


for i in range(n):
	if rank[i] == 0:
		par = i
		break

parent[par] = -1























def dfs(x):
	true_chil = []
	for c in chil[x]:
		if rank[c] == 1:
			true_chil.append(c)
		else:
			rank[c] -= 1
	for t in true_chil:
		parent[t] = x
		dfs(t)

	return

dfs(par)

for p in parent:
	print(p+1)

Solution (Python):
import sys

sys.setrecursionlimit(100001)

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)

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
indeg = defaultdict(int)
E = defaultdict(list)
parent = defaultdict(list)
for _ in range(N+M-1):
    a, b = map(int, input().split())
    indeg[b] += 1
    E[a].append(b)
    parent[b].append(a)

q = deque([v for v in range(1, N+1) if indeg[v] == 0])
top_sort = []
while q:
    v = q.popleft()
    top_sort.append(v)
    for u in E[v]:
        indeg[u] -= 1
        if indeg[u] == 0:
            q.append(u)
            
max_path_len = defaultdict(int)
max_path_parent = defaultdict(int)
for v in top_sort:
    if len(parent[v]) == 0:
        max_path_parent[v] = 0
        continue
    for u in parent[v]:
        if max_path_len[v] < max_path_len[u] + 1:
            max_path_len[v] = max_path_len[u] + 1
            max_path_parent[v] = u

for v  in max_path_parent.values():
    print(v)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

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


def topological_sort(g):
    topological_list = []
    visited = set()

    def dfs(n):
        for e in g[n]:
            if e not in visited:
                dfs(e)
        topological_list.append(n)
        visited.add(n)

    for i in range(len(g)):
        if i not in visited:
            dfs(i)

    return topological_list[::-1]


topological_order = topological_sort(G)


parents = [set(G_rev[i]) for i in range(N)]
for t in topological_order[::-1]:
    for p in G_rev[t]:
        parents[t] |= parents[p]


ans = [-1] * N
for t in topological_order:
    for child in G[t]:
        for p in G_rev[child]:
            if t in parents[p]:
                flg = True
                break
        else:
            ans[child] = t

for a in ans:
    print(a + 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)


n, m = map(int, input().split())
depth = [0 for _ in range(n)]
chil = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]

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


for i in range(n):
	if rank[i] == 0:
		par = i
		break

parent[par] = -1























def dfs(x):
	true_chil = []
	for c in chil[x]:
		if rank[c] == 1:
			true_chil.append(c)
		else:
			rank[c] -= 1
	for t in true_chil:
		parent[t] = x
		dfs(t)

	return

dfs(par)

for p in parent:
	print(p+1)

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

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)

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n,m = map(int, input().split())
    parent_dict = {}
    child_dict = {}
    len_tree = [0]*n
    for _ in range(n+m-1):
        a,b = map(int, input().split())
        try:
            parent_dict[b].add(a)
            len_tree[b-1]+=1
        except KeyError:
            parent_dict[b] = {a}
            len_tree[b-1] = 1
        try:
            child_dict[a].add(b)
        except KeyError:
            child_dict[a] = {b}
    parent_set = set(range(1,n+1))-set(parent_dict)
    root = list(parent_set)[0]
    check_list = [root]
    while len(check_list)>0:
        base = check_list[-1]
        check_list.pop(-1)
        try:
            for i in child_dict[base]:
                if len_tree[i-1]==1:
                    check_list.append(i)
                else:
                    len_tree[i-1]-=1
                    parent_dict[i]-={base}
        except KeyError:
            pass
    parent_dict[root] = [0]
    for i in range(1,n+1):
        print(list(parent_dict[i])[0])

Solution (Python):


import numpy as np
import scipy

from collections import defaultdict
from pprint import pprint

N, M = [int(x) for x in input().split(" ")]
lines = []
for i in range(N - 1 + M):
    a,b = [int(x) for x in input().split(" ")]
    lines.append([a,b])

in_num = [0 for x in range(N)]
out = [[] for x in range(N)]

for line in lines:
    A = line[0]
    B = line[1]
    in_num[B-1] += 1
    out[A-1].append(B-1)

roots = {} 
for i in range(N):
    if in_num[i] == 0:
        roots[i] = -1
        break

ans = [-1 for x in range(N)]
for i in range(N):
    for j in roots:
        ans[j] = roots[j]
    new_roots = {}
    for root in roots:
        for out_of_root in out[root]:
            in_num[out_of_root] -= 1
            if in_num[out_of_root] == 0:
                new_roots[out_of_root] = root
    roots = new_roots

for i in ans:
    print(i+1)

Solution (Python):
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 Q:
        i = Q.popleft()
        res.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return res

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)

Solution (Python):
import sys

sys.setrecursionlimit(100000000)

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

AB = [tuple(map(int, input().split())) for _ in range(N + M - 1)]

dprint = print


def BellmanFord(edges, num_v, source):
    
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source - 1] = 0

    
    for i in range(num_v):
        for edge in edges:
            if edge[0] != inf and dist[edge[1] - 1] > dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i == num_v - 1: return -1

    return dist


class Tree:
    def __init__(self, n):
        self.parent = set()
        self.child = set()
        self.rank = -1
        self.rank_fix = None
        self.current_parent = -1
        self.n = n

    def add_parent(self, i):
        self.parent.add(i)

    def add_child(self, i):
        self.child.add(i)

    def update_rank(self, v, parent_no):
        if self.rank >= v:
            return
        self.rank = v
        if self.current_parent != -1 and self.current_parent in self.parent:
            self.parent.remove(self.current_parent)
            trees[parent_no].child.remove(self.n)
        self.current_parent = parent_no
        for t in tuple(self.child):
            trees[t].update_rank(v + 1, self.n)

    def get_rank(self):
        if self.rank_fix:
            return self.rank_fix
        rank =  -1
        for p in self.parent:
            tmp_rank = trees[p].get_rank()
            if tmp_rank >rank:
                self.current_parent = p
                rank = tmp_rank
        self.rank_fix = rank + 1
        return self.rank_fix

    def __repr__(self):
        return "child" + str(self.child) + "rank:" + str(self.rank_fix) + " p:" + str(self.current_parent)


trees = [Tree(i) for i in range(N + 1)]
ans = [-1 for _ in range(N + 1)]
for a, b in AB:
    trees[a].add_child(b)
    trees[b].add_parent(a)

for i, t in enumerate(trees):
    if i != 0 and not t.parent:
        trees[0].add_child(i)
        trees[i].add_parent(0)
        break

for i in range(N):
    (trees[i + 1].get_rank())
    print(trees[i+1].current_parent)

Solution (Python):
from collections import defaultdict, deque
import copy
N, M = map(int, input().split())
cnt_in = defaultdict(int)
G = defaultdict(list)
G_rev = defaultdict(list)
for _ in range(N-1+M):
    a, b = map(int, input().split())
    G[a].append(b)
    G_rev[b].append(a)
    cnt_in[b] += 1
cnt = copy.deepcopy(cnt_in)
q = deque(v for v in range(1, N+1) if cnt_in[v] == 0)
res = []
while q:
    v = q.popleft()
    res.append(v)
    for nv in G[v]:
        cnt_in[nv] -= 1
        if cnt_in[nv] == 0:
            q.append(nv)
point2order = defaultdict(int)
dp = [0] * N
ans = [0] * N
for i in range(N):
    point2order[res[i]] = i
    for v in G_rev[res[i]]:
        if dp[point2order[v]]+1 >= dp[i]:
            dp[i] = dp[point2order[v]]+1
            ans[res[i]-1] = v
for elem in ans:
    print(elem)

Solution (Python):
N, M = map(int, input().split())
c = {}
d = {}
for i in range(1, N + 1):
	c[i] = []
	d[i] = 0
AB = []
for i in range(N - 1 + M):
	A, B = map(int, input().split())
	AB.append((A, B))
	c[A].append(B)
	d[B] += 1
s = []
for i in range(1, N + 1):
	if d[i] == 0:
		s.append(i)
t = []
while s != []:
	x = s.pop()
	t.append(x)
	for i in c[x]:
		d[i] -= 1
		if d[i] == 0:
			s.append(i)
p = {}
for i in range(N):
	p[t[i]] = i
ans = {}
for A, B in AB:
	if B in ans:
		if p[A] > p[ans[B]]:
			ans[B] = A
	else:
		ans[B] = A
for i in range(1, N + 1):
	if i in ans:
		print(ans[i])
	else:
		print(0)

Solution (Python):
from collections import defaultdict, deque

v, n = map(int, input().split())
n += v -1
es = [[int(x) for x in input().split()] for _ in range(n)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
f = [0]*(v+1)
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
            f[v2] = v1
for t in f[1:]:
    print(t)

Solution (Python):
from collections import defaultdict
from collections import Counter

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

A = defaultdict(list)
D = defaultdict(list)
DLen = defaultdict(int)
for i in range(N+M-1):
    a,b = map(int,input().split())
    A[a].append(b)
    
    DLen[b] += 1

start = 0
for i in range(1,N+1):
    if DLen[i] == 0:
        start = i
        break
        
D[start].append(0)
Search = [(start,A[start])]
Stepd = [start]

while Search:
    now,NEX = Search.pop()
    for s in NEX:
        if DLen[s]>=2:
            DLen[s] -= 1
        else:
            D[s] = [now]
            Stepd.append(s)
            Search.append((s,A[s]))
            
for i in range(1,N+1):
    print(D[i][0])

Solution (Python):
N,M=[int(x) for x in raw_input().split()]
inr=[[] for i in range(N+1)]
our=[[] for i in range(N+1)]
parent=[-1 for i in range(N+1)]
for i in range(N+M-1):
    a,b=[int(x) for x in raw_input().split()]
    inr[b].append(a)
    our[a].append(b)
sizein = [len(inr[x]) for x in range(1,N+1)]

root= sizein.index(0)+1
parent[root]=0
candset=[ [our[root],root] ]
while(len(candset)>0):
    newcandset=[]
    for cands in candset:
        for c in cands[0]:
            if len(inr[c])==1:
                parent[c]=cands[1]
                newcandset.append( [our[c],c] )
            else:
                inr[c].remove(cands[1])
        candset=newcandset[:]
for i in range(1,N+1):
    print parent[i]

Solution (Python):
from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        parent[i] = [-1]
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    if len(parent[v]) > 1:
        parent[v].remove(root) 
    else: que.append([root, v])
while que:
    u, V = que.popleft()
    for v in path[V]:
        if len(parent[v]) > 1:
            parent[v].remove(V)
        else:
            que.append([V, v])
for i in range(N):
    print(parent[i][0]+1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 5 + 100)

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
root = set(range(n))
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    root.discard(b)
root = root.pop()

parents = [set() for _ in range(n)]
q = deque([(root, -1)])

while q:
    v, p = q.popleft()
    parents[v].add(p)
    if len(parents[v]) > 1:
        continue
    q.extend((c, v) for c in links[v])

fixed = [-1] * n



q = deque([(root, -1)])
while q:
    v, p = q.popleft()
    pv = parents[v]
    pv.remove(p)
    if len(pv) == 0:
        fixed[v] = p
        q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in fixed))

Solution (Python):

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

Solution (Python):



from collections import deque

N, M = map(int, input().split())
G = [[] for i in range(N)]
P = [-2] * N
deg_in = [0] * N


def bfs(s):
    P[s] = -1
    q = deque()
    q.append(s)

    while len(q):
        u = q.popleft()
        for v in G[u]:
            deg_in[v] -= 1
            if deg_in[v] == 0:
                P[v] = u
                q.append(v)


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

    root = -1
    for i in range(N):
        if not deg_in[i]:
            root = i
            break

    bfs(root)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

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

Solution (Python):
from collections import defaultdict, deque

N, M = map(int, input().split())
v = N
n = N+M-1
es = [[int(x)-1 for x in input().split()] for _ in range(n)]
or_cop = [[] for i in range(N)]
for e in es:
    or_cop[e[1]].append(e[0])

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
root=res[0]            
LL = [[res[i],i] for i in range(N)]

LL=sorted(LL,key=lambda x: x[0])

for i in range(N):
    i_max=-1
    pare = -1
    if i==root:
        print(0)
    else:
        for cand in or_cop[i]:
            if LL[cand][1]>i_max:
                i_max=LL[cand][1]
                pare=cand
        print(pare+1)

Solution (Python):


N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N+M-1)]
ine = [[] * N for _ in range(N)]
oute = [[] * N for _ in range(N)]
for a, b in AB:
    ine[b-1].append(a-1)
    oute[a-1].append(b-1)
root = ine.index([])
v = [len(e) for e in ine]

ans = [0] * N
q = [(root, n) for n in oute[root]]
while q:
    nq = []
    for p, n in q:
        v[n] -= 1
        if v[n] == 0:
            ans[n] = p + 1
            nq += [(n, nn) for nn in oute[n]]
    q = nq

print("\n".join(map(str, ans)))

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

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

CLIST=[[] for i in range(N+1)]
PLIST=[[] for i in range(N+1)]

for x,y in EDGE:
    PLIST[y].append(x)
    CLIST[x].append(y)


ANSLIST=[-1]*(N+1)
check=[0]*(N+1)

for i in range(1,N+1):
    if PLIST[i]==[]:
        root=i
        break


ANSLIST[root]=0

QUE= deque()
QUE.append(root)

while QUE:
    x=QUE.pop()
    
    for next in CLIST[x]:
        count=0
        for j in PLIST[next]:
            if check[j]==1:
                continue
            count+=1
        if count==1:
            QUE.append(next)
            ANSLIST[next]=x
    check[x]=1

for a in ANSLIST[1:]:
    print(a)

Solution (Python):

from collections import deque

n,m=[int(i) for i in input().split()]
oya=[[] for i in range(n)]
ko=[[] for i in range(n)]
for i in range(n+m-1):
    aa,bb=[int(i)-1 for i in input().split()]

    oya[bb].append(aa)
    ko[aa].append(bb)


root=0
for i in range(n+m):
    if len(oya[i])==0:
        root=i
        break
oya[root]=['root']




d = deque([root])
while len(d) > 0:
    x = d.popleft()
    for i in ko[x]:
        if len(oya[i])!=1:
            oya[i].remove(x)
        else: d.append(i)




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

Solution (Python):
from collections import defaultdict, deque


def read():
    return int(input())


def readlist():
    return list(map(int, input().split()))


def readmap():
    return map(int, input().split())


N, M = readmap()
es = []
for _ in range(N - 1 + M):
    a, b = readmap()
    es.append([a, b])

v = N
n = N - 1 + M


outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

del res[0]
topo = res
inv_topo = [0] * N
for i in range(1, N+1):
    inv_topo[topo[i-1]-1] = i

parent = [0 for _ in range(N+1)]
for edge in es:
    child = edge[1]
    if parent[child] == 0:
        parent[child] = edge[0]
    else:
        if inv_topo[parent[child] - 1] < inv_topo[edge[0] - 1]:
            parent[child] = edge[0]

del parent[0]
for p in parent:
    print(p)