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

class Graph:
    def __init__(self, n_vertices, edges, directed=True):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            if self.directed:
                for u,v in self.edges:
                    adj[u].append(v)
            else:
                for u,v in self.edges:
                    adj[u].append(v)
                    adj[v].append(u)
            self._adj = adj
            return adj

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(N, edges):
    adj = Graph(N, edges, directed=True).adj
    parent = [-1]*N
    
    
    deg = [0]*N
    for u,v in edges:
        deg[v] += 1

    root = next(v for v,d in enumerate(deg) if d==0)

    topo = [-1]*N
    stack = [root]
    for i in range(N):
        v = stack.pop()
        topo[i] = v
        for u in adj[v]:
            deg[u] -= 1
            if deg[u] == 0:
                stack.append(u)

    dist = [0]*N
    for v in topo:
        d = dist[v]
        for u in adj[v]:
            dist[u] = max2(dist[u], d+1)

    parent = [-1]*N
    for v,l in enumerate(adj):
        d = dist[v]+1
        for u in l:
            if d == dist[u]:
                parent[u] = v
    return (p+1 for p in parent)




if __name__ == '__main__':
    N,M = map(int,readline().split())
    m = map(lambda x: int(x)-1, read().split())
    edges = list(zip(m,m))
    print(*solve(N,edges), sep='\n')

Solution (Python):
n,m=map(int,input().split())
d=[0 for i in range(n)]
e=[[] for i in range(n)]
for i in range(n+m-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  d[b]+=1
  
for i in range(n):
  if d[i]==0:
    root=i

s=[root]
mer=[-1 for i in range(n)]
mer[root]=0
c=[0 for i in range(n)]
while s:
  ns=[]
  for i in s:
    for j in e[i]:
      c[j]+=1
      if c[j]==d[j]:
        mer[j]=i+1
        ns.append(j)
  s=ns
print("\n".join(map(str,mer)))

Solution (Python):
from collections import deque
def tsort(In,G,N):
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    return l

N,M=map(int,input().split())
In=[0]*N
In_Edge=[[] for _ in range(N)]

G=[[] for _ in range(N)]

for _ in range(N-1+M):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    In[b]+=1
    In_Edge[b].append(a)

T_sorted=tsort(In,G,N)
P=[-1]*N
for i,v in enumerate(T_sorted):
    P[v]=i
ans=[-1]*N
for i in reversed(range(N)):
    v=T_sorted[i]
    if not In_Edge[v]:
        ans[v]=0
        continue
    In_Edge[v].sort(key=lambda x:P[x])
    ans[v]=In_Edge[v][-1]+1
print(*ans,sep='\n')

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, UV):
    g = defaultdict(list)
    fin = Counter()
    for u, v in UV:
        g[u].append(v)
        fin[v] += 1

    r = -1
    for v in range(1, N+1):
        n = fin[v]
        if n == 0:
            r = v
            break

    a = defaultdict(lambda: None)
    q = deque([r])
    a[r] = 0
    while q:
        u = q.popleft()
        for v in g[u]:
            fin[v] -= 1
            if fin[v] == 0:
                a[v] = u
                q.append(v)

    ans = [a[i] for i in range(1, N+1)]
    return ans


def main():
    N, M = read_int_n()
    UV = [read_int_n() for _ in range(N-1+M)]
    print(*slv(N, M, UV), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[] for i in range(n)]
edges_r = [[] for i in range(n)]
for i in range(n+m-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges_r[b].append(a)


s = 0
ks = []
for i,e in enumerate(edges_r):
    if len(e) == 0:
        s = i
    ks.append(len(e))

parents = [-1] * n
INF = 1 << 60
q = deque([s])
while len(q) > 0:
    u = q.popleft()
    for v in edges[u]:
        
        ks[v] -= 1
        
        
        if ks[v] == 0:
            parents[v] = u
            q.appendleft(v) 

for p in parents:
    print(p+1)

Solution (Python):
N,M=map(int,input().split())
G1 = [set() for _ in range(N)]
G2 = [set() for _ in range(N)]

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

inc = [len(G2[i]) for i in range(N)]
S = {i for i, c in enumerate(inc) if c == 0}
L = []

while S:
    n = S.pop()
    L.append(n)
    for m in G1[n]:
        inc[m] -= 1
        if inc[m] == 0:
            S.add(m)

d = [-1]*N
d[L[0]]=0

ans=[0]*N
for v in L[1:]:
  MAX=0
  argmax=-1
  for p in G2[v]:
    if d[p] != -1 and MAX<d[p]+1:
      MAX=d[p]+1
      argmax=p+1
  d[v] = MAX
  ans[v]=argmax

print(*ans)

Solution (Python):

from collections import deque
import sys
def main(N, M, G, I, root):
    P = [-1] * N
    q = deque()
    q.append(root)
    while q:
        v = q.popleft()
        for to in G[v]:
            I[to] -= 1
            if I[to] == 0:
                P[to] = v
                q.append(to)
    for p in P:
        print(p + 1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    I = [0] * N
    for _ in range(N - 1 + M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        I[b] += 1
    main(N, M, G, I, I.index(0))

Solution (Python):

from collections import deque
import sys
def main(N, M, G, R, I, root):
    P = [-1] * N
    D = [-1] * N
    D[root] = 0
    q = deque()
    q.append(root)
    while q:
        v = q.popleft()
        for to in G[v]:
            I[to] -= 1
            if I[to] == 0:
                D[to] = D[v] + 1
                P[to] = v
                q.append(to)
    for p in P:
        print(p + 1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    R = [[] for _ in range(N)]
    I = [0] * N
    for _ in range(N - 1 + M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        R[b].append(a)
        I[b] += 1
    main(N, M, G, R, I, I.index(0))

Solution (Python):

from collections import deque
import sys
def main(N, M, G, R, I, root):
    P = [-1] * N
    D = [-1] * N
    D[root] = 0
    q = deque()
    q.append(root)
    while q:
        v = q.popleft()
        for to in G[v]:
            I[to] -= 1
            if I[to] == 0:
                p = pd = -1
                for r in R[to]:
                    if D[r] > pd:
                        pd = D[r]
                        p = r
                D[to] = pd + 1
                P[to] = p
                q.append(to)
    for p in P:
        print(p + 1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    R = [[] for _ in range(N)]
    I = [0] * N
    for _ in range(N - 1 + M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        R[b].append(a)
        I[b] += 1
    main(N, M, G, R, I, I.index(0))

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

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    ind = [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)
        ind[b] += 1

    from collections import deque
    q = deque([])
    order = []
    par = [0]*n
    for i in range(n):
        if ind[i] == 0:
            q.append(i)
    while q:
        v = q.popleft()
        order.append(v)
        for u in g[v]:
            ind[u] -= 1
            if ind[u] == 0:
                par[u] = v+1
                q.append(u)
    print(*par, sep='\n')

if __name__ == '__main__':
    main()

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

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    ind = [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)
        ind[b] += 1

    from collections import deque
    q = deque([])
    order = []
    par = [0]*n
    for i in range(n):
        if ind[i] == 0:
            q.append(i)
    while q:
        v = q.popleft()
        order.append(v)
        for u in g[v]:
            ind[u] -= 1
            if ind[u] == 0:
                par[u] = v+1
                q.append(u)
    print(*par, sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, M = in_nn()

    dim = [0] * N
    edge = [set() for _ in range(N)]
    for i in range(N + M - 1):
        x, y = in_nn()
        x, y = x - 1, y - 1
        dim[y] += 1
        edge[x].add(y)

    root = dim.index(0)
    q = deque()
    q.append(root)

    while q:
        v = q.popleft()
        delete = set()
        for nv in edge[v]:
            if dim[nv] > 1:
                dim[nv] -= 1
                delete.add(nv)
            else:
                q.append(nv)
        edge[v] -= delete

    ans = [-1] * N

    for v1 in range(N):
        for v2 in edge[v1]:
            ans[v2] = v1

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N,M=map(int,input().split())

outs = [[] for _ in range(N+1)]
outs_rev = [[] for _ in range(N+1)]
ins = [0]*(N+1)
for _ in range(N+M-1):
  v1,v2=map(int,input().split())
  outs[v1].append(v2)
  outs_rev[v2].append(v1)
  ins[v2] += 1



q = deque(v1 for v1 in range(N+1) 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)


res_rev=[0]*(N+1)
for i in range(N):
  res_rev[res[i]]=i


answer_list=[0]*(N+1)
for i in range(1,N+1):
  r=res[i]
  if not outs_rev[r]:
    answer_list[r]=0
  else:
    max_v=-1
    max_index=-1
    for rr in outs_rev[r]:
      ind=res_rev[rr]
      if ind>max_index:
        max_v=res[ind]
        max_index=ind
  
    answer_list[r]=max_v
    

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

Solution (Python):
from collections import defaultdict, deque
N,M=map(int,input().split())

outs = defaultdict(list)
outs_rev = defaultdict(list)
ins = defaultdict(int)
for _ in range(N+M-1):
  v1,v2=map(int,input().split())
  outs[v1].append(v2)
  outs_rev[v2].append(v1)
  ins[v2] += 1



q = deque(v1 for v1 in range(1,N+1) 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)


res_rev=[0]*N
for i in range(N):
  res_rev[res[i]-1]=i


answer_list=[0]*N
for i in range(N):
  r=res[i]
  if not outs_rev[r]:
    answer_list[r-1]=0
  else:
    max_v=-1
    max_index=-1
    for rr in outs_rev[r]:
      ind=res_rev[rr-1]
      if ind>max_index:
        max_v=res[ind]
        max_index=ind
  
    answer_list[r-1]=max_v
    

for ans in answer_list:
  print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() 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)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n,m=LI()
G=[[]for _ in range(n)]
cnt=[0]*n
for _ in range(n-1+m):
    a,b=LI()
    G[a-1]+=[b-1]
    cnt[b-1]+=1

r=cnt.index(0)
D=[0]*n
q=deque([r])
ans=[0]*n
while q:
    u=q.popleft()
    for v in G[u]:
        cnt[v]-=1
        ans[v] = u + 1
        if not cnt[v]:
            q+=[v]


print(*ans,sep="\n")

Solution (Python):
from collections import deque
n, m = map(int, input().split())
edge = [[] for i in range(n)]
cnt = [0] * n
ans = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    cnt[b - 1] += 1
Q = deque([cnt.index(0)])
while Q:
    p = Q.popleft()
    for u in edge[p]:
        cnt[u] -= 1
        if cnt[u] == 0:
            ans[u] = p + 1
            Q.append(u)
for i in range(n):
    print(ans[i])

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1+M)]

es = [[] for _ in range(N)]
indeg = [0] * N
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    indeg[b] += 1

from collections import deque
q = deque()
for i in range(N):
    if indeg[i] == 0:
        q.append(i)

ans = [0] * N
while q:
    v = q.popleft()
    for to in es[v]:
        indeg[to] -= 1
        if indeg[to] == 0:
            q.append(to)
            ans[to] = v+1
print(*ans, sep='\n')

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict
    n, m = map(int, readline().split())
    edge_to = defaultdict(set)
    edge_from = defaultdict(set)
    from_cnt = [0] * n
    par = [-1] * n

    for _ in range(n + m - 1):
        a, b = map(int, readline().split())
        a, b = a - 1, b - 1
        edge_to[a].add(b)
        edge_from[b].add(a)
        from_cnt[b] += 1

    root = from_cnt.index(0)
    par[root] = 0

    que = deque()
    que.append(root)

    while que:
        cur = que.popleft()
        for nx in edge_to[cur]:
            if from_cnt[nx] == 1:
                par[nx] = cur + 1
                que.append(nx)
            else:
                from_cnt[nx] -= 1

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


if __name__ == '__main__':
    main()

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m = map(int,ipt().split())
    go = [[] for i in range(n+1)]
    cm = [[] for i in range(n+1)]
    for i in range(n+m-1):
        a,b = map(int,ipt().split())
        cm[b].append(a)
        go[a].append(b)

    prnt = [-1]*(n+1)
    q = queue.Queue()
    for i in range(1,n+1):
        if not cm[i]:
            prnt[i] = 0
            for j in go[i]:
                q.put((j,i))
            break

    while not q.empty():
        qn,qp = q.get()

        f = True
        for i in cm[qn]:
            if prnt[i] == -1 or prnt[i] == qp:
                f = False
                break

        if f:
            prnt[qn] = qp
            for i in go[qn]:
                q.put((i,qn))

    for i in prnt[1::]:
        print(i)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def topological(N, LIST): 
    incnt = [0] * N
    CHILD = [set() for _ in range(N)]
    for a, b in LIST:
        CHILD[a - 1].add(b - 1)
        incnt[b - 1] += 1
    
    TPLGSORT = []
    que = deque([i for i, num in enumerate(incnt) if num == 0])
    while len(que) > 0:
        q = que.popleft()
        for i in CHILD[q]:
            incnt[i] -= 1
            if incnt[i] == 0:
                que.append(i)
        TPLGSORT.append(q)
    return TPLGSORT, CHILD


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n + m - 1)]

tplg, child = topological(n, ab)
ans = [0] * n
for i in tplg:
    for j in child[i]:
        ans[j] = i + 1
print(*ans, sep='\n')

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    visited = [False] * n
    visited[0] = True
    que = deque([0])
    while que:
        v = que.popleft()
        if len(edge_r[v]) == 0:
            root = v
            break
        for u in edge_r[v]:
            if not visited[u]:
                visited[u] = True
                que.appendleft(u)

    cnt = [len(edge_r[i]) for i in range(n)]
    res = [[] for _ in range(n)]
    res[root].append(0)
    que = deque([root])
    while que:
        v = que.popleft()
        for u in edge[v]:
            if cnt[u] > 1:
                cnt[u] -= 1
            else:
                cnt[u] = 0
                que.appendleft(u)
                res[u].append(v + 1)

    for i in res:
        print(*i)


if __name__ == '__main__':
    resolve()

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

def main():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    parcount = [-1]*n
    for i in range(n+m-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        parcount[b-1] += 1
    
    for i in range(n):
        if parcount[i] == -1:
            root = i
            break
    
    par = [0]*n
    dist = [0]*n
    not_yet = deque([root])
    while not_yet:
        key = not_yet.popleft()
        for v in tree[key]:
            if parcount[v]:
                parcount[v] -= 1
                continue
            par[v] = key+1
            dist[v] = dist[key]+1
            not_yet.append(v)
    
    for p in par:
        print(p)
 
    
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

n, m = map(int, input().split())
check = [0 for _ in range(n)]
edges = [[] for _ in range(n)]

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

rood = check.index(0)
queue = deque()
ans = [0 for _ in range(n)]
queue.append(rood)
while queue:
    pos = queue.popleft()
    for n_pos in edges[pos]:
        check[n_pos] -= 1
        if check[n_pos] == 0:
            queue.append(n_pos)
            ans[n_pos] = pos + 1
        
for pos in ans:
    print(pos)

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
lis=[tuple(map(int,input().split()))for _ in range(n+m-1)]
node_in=[0]*n
node=[[]for i in range(n)]
for x,y in lis:
	node_in[y-1]+=1
	node[x-1].append(y-1)
for i in range(n):
	if node_in[i]==0:
		root=i
		break
ans=[-1]*n
ans[root]=0
stack=[root]
while stack:
	r=stack.pop()
	for x in node[r]:
		node_in[x]-=1
		if node_in[x]==0:
			stack.append(x)
			ans[x]=r+1
for x in ans:
	print(x)

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    prnt_cnt = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        prnt_cnt[b] += 1

    root_idx = prnt_cnt.index(0)

    que = collections.deque([root_idx])

    while que:
        q = que.popleft()
        for ei in e[q]:
            prnt_cnt[ei] -= 1
            if prnt_cnt[ei] == 0:
                ans[ei] = q
                que.append(ei)

    for ansi in ans:
        print(ansi + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    root = [True for _ in range(n)]
    prnt_cnt = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        root[b] = False
        prnt_cnt[b] += 1

    root_idx = root.index(True)

    que = collections.deque([root_idx])

    while que:
        q = que.popleft()

        for ei in e[q]:
            ans[ei] = q
            prnt_cnt[ei] -= 1
            if prnt_cnt[ei] == 0:
                que.append(ei)

    for ansi in ans:
        print(ansi + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import copy



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    root = [True for _ in range(n)]
    prnt_cnt = [0 for _ in range(n)]
    ans = [-1 for _ in range(n)]

    for _ in range(n - 1 + m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        root[b] = False
        prnt_cnt[b] += 1

    root_idx = root.index(True)

    que = collections.deque([root_idx])

    while que:
        q = que.popleft()

        for ei in e[q]:
            ans[ei] = q
            prnt_cnt[ei] -= 1
            if prnt_cnt[ei] == 0:
                que.append(ei)

    for ansi in ans:
        print(ansi + 1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

graph = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
in_degree = [0] * n
out_degree = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph2[b].append(a)
    in_degree[b] += 1
    out_degree[a] += 1

v_root = in_degree.index(0)

depth = [-1] * n
ans = [0] * n
depth[v_root] = 0


def dfs(v):
    if depth[v] == -1:
        for v_par in graph2[v]:
            d = dfs(v_par)
            if depth[v] < d + 1:
                depth[v] = d + 1
                ans[v] = v_par + 1
    return depth[v]


for i in range(n):
    if out_degree[i] == 0:
        
        _ = dfs(i)

print(*ans, sep='\n')

Solution (Python):
N,M=map(int, input().split())
T,F=[[]for i in range(N)],[[]for i in range(N)]
for i in range(N-1+M):
  a,b=map(int, input().split())
  a-=1
  b-=1
  T[a].append(b)
  F[b].append(a)
  
for i in range(N):
  if len(F[i])==0:
    R=i
    break
    
ans=[-1]*N
ans[R]=0

from collections import deque
q=deque([])
q.append(R)
s=set()
while q:
  now=q.popleft()
  s.add(now)
  for i in T[now]:
    if ans[i]==-1:
      c=0
      for j in F[i]:
        if j not in s:
          c=1
          break
      if c==0:
        ans[i]=now+1
        q.append(i)
        
for i in ans:
  print(i)

Solution (Python):
N,M=map(int, input().split())
T,F=[[]for i in range(N)],[[]for i in range(N)]
for i in range(N-1+M):
  a,b=map(int, input().split())
  a-=1
  b-=1
  T[a].append(b)
  F[b].append(a)
  
for i in range(N):
  if len(F[i])==0:
    R=i
    break
    
ans=[-1]*N
ans[R]=0

from collections import deque
q=deque([])
q.append(R)
s=set()
while q:
  now=q.popleft()
  s.add(now)
  for i in T[now]:
    if ans[i]==-1:
      c=0
      for j in F[i]:
        if j not in s:
          c=1
          break
      if c==0:
        ans[i]=now+1
        q.append(i)
        
for i in ans:
  print(i)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] 
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: 
        return dp[v]

    for i in co[v]:
        x = memo(i) + 1
        if x > dp[v]:
            parent[v] = i + 1
            dp[v] = x

    return max(dp[v], 0)

parent = [0] * n
for i in range(n):
    memo(i)


for i in parent:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] 
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: 
        return dp[v]
    a = 0
    for i in co[v]:
        a = max(a, memo(i) + 1)
    dp[v] = a
    return a

for i in range(n):
    memo(i)

parent = [0] * n
for v in range(n):
    for e in es[v]:
        if dp[v] + 1 == dp[e]:
            parent[e] = v + 1

for i in parent:
    print(i)