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):
n,m=map(int,input().split())
oy=[set() for i in range(n+1)]
ko=[set() for i in range(n+1)]
ans= [0 for i in range(n+1)]
for i in range(m+n-1):
  a,b=map(int,input().split())
  oy[b]|={a}
  ko[a]|={b}
  
for i in range(1,len(oy)):
  if oy[i]==set():
    break

l=[[i,ko[i]]]
while l:
  o,k=l.pop()
  for i in k:
    oy[i].remove(o)
    if len(oy[i])==0:
      l.append([i,ko[i]])
      ans[i]=o
for i in ans[1:]:
  print(i)

Solution (Python):
import queue
N, M = map(int, input().split())
ParentNum = [None] * N
EdgeFrom = [[] for _ in range(N)]
EdgeTo = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    EdgeFrom[B-1].append(A-1)
    EdgeTo[A-1].append(B-1)

for i in range(N):
    if not EdgeFrom[i]:
        ParentNum[i] = 0
        ParentNode = i
        break

Q = queue.Queue()
Q.put(ParentNode)
while not Q.empty():
    currentNode = Q.get()
    for node in EdgeTo[currentNode]:
        if len(EdgeFrom[node]) > 1:
            EdgeFrom[node].remove(currentNode)
        else:
            ParentNum[node] = currentNode + 1
            Q.put(node)
for item in ParentNum:
    print(item)

Solution (Python):
N, M = map(int, input().split())
to = [0] * (N+1)
E = [set() for i in range(N+1)]
for i in range(N+M-1):
    A, B = map(int, input().split())
    E[A].add(B)
    
    to[B] += 1
A = [0] * (N+1)
for root, t in enumerate(to[1:], 1):
    if t==0:
        break
Open = {root}

while len(Open)>0:

    root = Open.pop()

    for r in E[root]:
        
        to[r]-=1
        if to[r]==0:
            A[r]=root
            Open.add(r)
for a in A[1:]:
    print(a)

Solution (Python):
import collections

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

in_graph = [[] for i in range(n)]
out_graph = [[] for i in range(n)]
in_count = [0] * n
out_count = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    out_graph[a].append(b)
    out_count[a] += 1
    in_graph[b].append(a)
    in_count[b] += 1
root = in_count.index(0)
ranks = [0] * n
parent = [0] * n
dq = collections.deque()
for i in range(n):
    if out_count[i] == 0:
        dq.append(i)
rank = n
while dq:
    v = dq.popleft()
    ranks[v] = rank
    rank -= 1
    for nv in in_graph[v]:
        out_count[nv] -= 1
        if out_count[nv] == 0:
            dq.append(nv)

for i in range(n):
    max_v = -1
    max_rank = -1
    for v in in_graph[i]:
        if max_rank < ranks[v]:
            max_rank = ranks[v]
            max_v = v
    print(max_v+1)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
H=[[] for i in range(N)]
for i in range(N-1+M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    H[b-1].append(a-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
tbl=[-1 for i in range(N)]
for i in range(N):
    tbl[res[i]]=i
ans=[0 for i in range(N)]
for i in range(1,N):
    L=[]
    for p in H[res[i]]:
        L.append((tbl[p],p))
    ans[res[i]]=max(L)[1]+1
for i in ans:
    print(i)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter, deque
from bisect import *

setrecursionlimit(10**7)

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

def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = [[] for _ in range(N)]
rem = [0] * N
for i in range(N-1+M):
  a, b = reads()
  edges[a-1].append(b-1)
  rem[b-1] += 1

root = next(i for i in range(N) if rem[i] == 0)

par = [-1] * N
que = deque([root])

while len(que) != 0:
  x = que.popleft()
  for y in edges[x]:
    par[y] = x
    rem[y] -= 1
    if rem[y] == 0:
      que.append(y)

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

Solution (Python):
from sys import stdin, stdout
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * (n - 1 + m)))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(n - 1 + m):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        la[x] = j + 1
        j += 2
    st = []
    pu = st.append
    po = st.pop
    col = [None] * (n + 1)
    top = []
    tpu = top.append
    for i in xrange(1, n + 1):
        if col[i] is not None:
            continue
        pu((i, la[i]))
        while st:
            x, y = po()
            if col[x] is None:
                col[x] = 1
            while y is not None and col[dat[y]]:
                y = xt[y]
            if y is None:
                tpu(x)
            else:
                pu((x, xt[y]))
                pu((dat[y], la[dat[y]]))
    rto = [0] * (n + 1)
    for i, x in enumerate(top):
        rto[x] = i
    par = [0] * (n + 1)
    rto[0] = n + 1
    for i in xrange(1, n + 1):
        y = la[i]
        while y is not None:
            z = dat[y]
            if rto[par[z]] > rto[i]:
                par[z] = i
            y = xt[y]
    stdout.write(''.join('%d\n' % x for x in par[1:]))
main()

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

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





dp = [-1] * N
def calc(i):
    if dp[i] >= 0:
        return dp[i]
    if not P[i]:
        dp[i] = 0
        return 0
    ma = -1
    for p in P[i]:
        ma = max(ma, calc(p))
    dp[i] = ma+1
    return ma+1

for i in range(N):
    calc(i)

for i in range(N):
    if dp[i] == 0:
        print(0)
    else:
        for p in P[i]:
            if dp[p] == dp[i] - 1:
                print(p+1)
                break

Solution (Python):
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(N-1+M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    Lin[b]+=1
    table[a].append(b)
M=[0]*N
H=deque()
s=-1
for i in range(N):
    if Lin[i]==0:
        s=i
        break
H.append(s)
while H:
    x=H.popleft()
    for y in table[x]:
        Lin[y]-=1
        if Lin[y]==0:
            M[y]=x+1
            H.append(y)
print('\n'.join(map(str,M)))

Solution (Python):
from collections import deque

readline = open(0).readline
N, M = map(int, readline().split())
deg = [0]*N
G = [[] for i in range(N)]
RG = [[] for i in range(N)]
for i in range(N-1+M):
    a, b = map(int, readline().split())
    deg[b-1] += 1
    G[a-1].append(b-1)
    RG[b-1].append(a-1)

que = deque()
for i in range(N):
    if deg[i] == 0:
        que.append(i)

res = ["0\n"]*N
L = [0]*N
while que:
    v = que.popleft()
    r = 0; x = None
    for w in RG[v]:
        if r < L[w] + 1:
            r = L[w] + 1
            x = w
    if x is not None:
        L[v] = r
        res[v] = "%d\n" % (x+1)
    for w in G[v]:
        deg[w] -= 1
        if deg[w] == 0:
            que.append(w)

open(1, 'w').writelines(res)

Solution (Python):
def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())
import heapq

n, m = mi()
g = [[] for i in range(n + 1)]
deg = [0] * (n + 1)
for i in range(n + m - 1):
    u, v = mi()
    g[u].append(v)
    deg[v] += 1

pq = []
for u in range(1, n + 1):
    if deg[u] == 0:
        pq.append((0, u))
par = [0] * (n + 1)
dist = [0] * (n + 1)
while pq:
    d, u = heapq.heappop(pq)
    if d > deg[u]: continue
    for v in g[u]:
        if dist[v] < dist[u] + 1:
            dist[v] = dist[u] + 1
            par[v] = u
        deg[v] -= 1
        heapq.heappush(pq, (deg[v], v))

print(*par[1:], sep='\n')

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = collections.defaultdict(set)
    f = collections.defaultdict(set)
    for _ in range(n+m-1):
        a,b = LI_()
        e[a].add(b)
        f[b].add(a)

    s = -1
    for k in e.keys():
        if len(f[k]) == 0:
            s = k
            break

    r = [None] * n
    r[s] = 0
    al = set([s])
    q = set([s])
    while q:
        u = set()
        for c in q:
            for d in e[c]:
                if len(f[d] - al) == 0:
                    u.add(d)
                    r[d] = c + 1
        al |= u
        q = u

    return '\n'.join(map(str, r))



print(main())