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: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None

def sigma_(a, b, n):
    return (a + b) * n // 2

def main():
    N, M = li_input()
    V = [li_input() for _ in range(N+M-1)]

    # print("N,M", N, M)
    # print("V", V)

    Link = [[] for _ in range(N+1)]
    iLink = [[] for _ in range(N+1)]

    for v in V:
        sv, se = v
        Link[sv].append(se)
        iLink[se].append(sv)

    # 根を求める
    distV = []
    for v in V:
        distV.append(v[1])

    distV = list(set(distV))
    root = sigma_(1, N, N) - sum(distV)

    # print("root", root)

    A = [0] * N

    Layer = [[root]]

    parent_nodes = [root]
    i = 1
    while len(parent_nodes) != 0:
        Layer.append([])
        new_parent_nodes = []

        j = 0
        while j < len(V):
            sv, ev = V[j]

            if sv in parent_nodes:
                Layer[i].append(ev)
                new_parent_nodes.append(ev)
            
            j += 1

        i += 1
        parent_nodes = new_parent_nodes

    Layer = Layer[:-1]
    Kakutei = []

    i = len(Layer) - 1
    while i >= 0:
        L = Layer[i]
        for l in L:
            if l in Kakutei:
                continue
            maybe_parents = iLink[l]

            for maybe_parent in maybe_parents:
                if maybe_parent in Layer[i-1]:
                    A[l-1] = maybe_parent
                    Kakutei.append(l)
                    break
        
        i -= 1
    
    for a in A:
        print(a)


                


main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge_from = [[] for _ in range(N+1)]
edge_to = [[] for _ in range(N+1)]
ans = [-1]*(N+1)
arr = []
child = set()
parent = -1
for _  in range(N-1+M):
    go,to = map(int,input().split())
    edge_from[go].append(to)
    edge_to[to].append(go)
    arr.append((go,to))
    child.add(to)
for i in range(1,N+1):
    if i not in child:
        parent = i
stack = [parent]
distance = [-1]*(N+1)
distance[parent] = 0
while stack:
    v = stack.pop()
    for u in edge_from[v]:
        distance[u] = max(distance[v] + 1,distance[u])
        stack.append(u)
for i in range(1,N+1):
    if i == parent :
        ans[i] = 0
    else:
        for j in edge_to[i]:
            if distance[j] == distance[i] -1:
                ans[i] = j
                break
for i in range(1,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
xs = {}
used = [0] * N
for i in range(N+M-1):
  a, b = map(int, input().split())
  used[b-1] = 1
  if a in xs:
  	xs[a].append(b)
  else:
    xs[a] = [b]

root = used.index(0)+1
queue = [root]
while queue:
  c = queue.pop(0)
  if c in xs:
    for x in xs[c]:
      used[x-1] = c
      queue.append(x)

for x in used:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[[] for i in range(n+1)]
rt=[None for i in range(n+1)]
s=set([i+1 for i in range(n)])
for i in range(n-1+m):
    a,b=map(int,input().split())
    l[a].append(b)
    s.discard(b)
root=s.pop()
rt[root]=0
tochk=[[l[root],root]]
while tochk!=[]:
    temp=[]
    for ll in tochk:
        for v in ll[0]:
            rt[v]=ll[1]
            if len(l[v])>0:
                temp.append([l[v],v])
    tochk=temp
for i in range(n):
    print(rt[i+1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
C = [[] for i in range(N)]
P = [[] for i 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)
R = [0] * N
for i in range(N):
  R[i] = -len(P[i])
  if R[i] == 0:
    Q = [i]
while Q:
  q = Q.pop(0)
  for c in C[q]:
    R[c] += 1
    if R[c] == 0:
      R[c] = q + 1
      Q.append(c)
for r in R:
  print(r)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque
def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    isRoot = [True] * n
    for _ in range(n - 1 + m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        isRoot[b] = False

    for i in range(n):
        if isRoot[i]:
            root = i
            break
    INF = 10 ** 20
    que = deque()
    que.append((0, root, -1))
    height = [-INF] * n
    parent = [None] * n
    def search(stack):
        score, node, par = que.popleft()
        if -score > height[node]:
            height[node] = -score
            parent[node] = par
            for to in edges[node]:
                que.append((score - 1, to, node))

    while que:
        search(que)

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

main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
#sys.setrecursionlimit(10**8)
from collections import deque

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)]
visited = [False 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

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

parent[par] = -1

def bfs(x):
	que = deque([[x, 0]])
	while que:
		l = que.pop()
		y, d = l[0], l[1]
		if d < depth[y]:
			continue
		for c in chil[y]:
			if depth[c] == -1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])
			elif depth[c] < d+1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])

	return

bfs(par)
#def dfs(x, d):
#	for c in chil[x]:
#		if depth[c] == -1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#		elif depth[c] < d+1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#
#	return
#
#dfs(par, 0)

for p in parent:
	print(p+1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

sys.setrecursionlimit(300000)

N, M = ln()

parent = collections.defaultdict(list)
child = collections.defaultdict(list)

for i in xrange(N - 1 + M):
    a, b = ln()
    parent[b].append(a)
    child[a].append(b)

top = 1
while parent[top]:
    top = parent[top][0]

unique_root = [0] * (N + 1)
v_depth = [0] * (N + 1)
def f(cur, depth, prev):
    if v_depth[cur] < depth or prev == 0:
        unique_root[cur] = prev
        v_depth[cur] = depth
        for c in child[cur]:
            f(c, depth + 1, cur)

f(top, 0, 0)

print '\n'.join(map(str, unique_root[1:]))

Submission status: Time Limit Exceeded

Solution code:
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
        ans[i] = -1
    
que = deque()
for v in path[root]:
    que.append([root, v])
while que:
    u, V = que.popleft()
    ans[V] = u
    for v in path[V]:
        que.append([V, v])

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

Submission status: Time Limit Exceeded

Solution code:
#import sys
#sys.setrecursionlimit(10**8)
from collections import deque

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)]
visited = [False 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

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

parent[par] = -1

def bfs(x):
	que = deque([[x, 0]])
	while que:
		l = que.pop()
		y, d = l[0], l[1]
		for c in chil[y]:
			if depth[c] == -1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])
			elif depth[c] < d+1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])

	return

bfs(par)
#def dfs(x, d):
#	for c in chil[x]:
#		if depth[c] == -1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#		elif depth[c] < d+1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#
#	return
#
#dfs(par, 0)

for p in parent:
	print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
P = [set() for _ in range(N + 1)]
for a, b in AB:
    G[a].add(b)
    P[b].add(a)
for i in range(1, N):
    if len(P[i]) == 0:
        break


def bellman_ford(V, G, i):
    ans = [0] * V
    INF = float('inf')
    D = [INF] * V
    D[i] = 0
    for _ in range(1, V):
        update = False
        for p in range(1, V):
            for c in G[p]:
                if D[p] != INF and D[c] > D[p] - 1:
                    D[c] = D[p] - 1
                    ans[c] = p
                    update = True
        if not update:
            return ans
        if _ == V:
            return False


D = bellman_ford(N + 1, G, i)[1:]
[print(_) for _ in D]

Submission status: Time Limit Exceeded

Solution code:
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
        ans[i] = -1
    
que = deque()
que.append([root, path[root]])
while que:
    u, V = que.pop()
    for child in V:
        ans[child] = u
        que.append([child, path[child]])

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
C = [[] for i in range(N)]
P = [[] for i 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)
R = [-1] * N
for i in range(N):
  if P[i] == []:
    Q = [i]
    break
while Q:
  q = Q.pop(0)
  for c in C[q]:
    if len(P[c]) > 1:
      P[c].remove(q)
    else:
      R[c] = q
      Q.append(c)
for r in R:
  print(r + 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import numpy as np
from collections import deque


def solve():
    N, M = map(int, input().split())
    TO = np.zeros(N)
    G = [set() for _ in range(N)]
    for _ in range(N+M-1):
        f, t = map(int, input().split())
        f -= 1
        t -= 1
        TO[t] += 1
        G[f].add(t)
    start = TO.argmin()

    parent = np.zeros(N, dtype=int)
    # path = np.zeros(N)
    checked = set()
    # 探索
    que = deque([start])
    while len(que):
        fr = que.popleft()
        for to in G[fr]:
            if to not in checked:
                parent[to] = fr
                # path[to] = path[fr] + 1
                que.append(to)
    for i in range(N):
        if i == start:
            print(0)
        else:
            print(parent[i]+1)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N, M = inpl()
Edge = defaultdict(lambda: [])
Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
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)]
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
    
que = deque()
que.append([root, path[root]])
while que:
    u, V = que.pop()
    for child in V:
        parent[child] = u
        que.append([child, path[child]])

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify

def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    isRoot = [True] * n
    for _ in range(n - 1 + m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        isRoot[b] = False

    for i in range(n):
        if isRoot[i]:
            root = i
            break
    INF = 10 ** 20
    stack = [(0, root, -1)]
    heapify(stack)
    height = [-INF] * n
    parent = [None] * n
    def search(stack):
        score, node, par = heappop(stack)
        if -score > height[node]:
            height[node] = -score
            parent[node] = par
            for to in edges[node]:
                heappush(stack,(score - 1, to, node))

    while stack:
        search(stack)

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

main()

Submission status: Time Limit Exceeded

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

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

parent[par] = -1

def dfs(x, d):
	for c in chil[x]:
		if depth[c] == -1:
			depth[c] = d+1
			parent[c] = x
			dfs(c, d+1)
		elif depth[c] < d+1:
			depth[c] = d+1
			parent[c] = x
			dfs(c, d+1)

	return

dfs(par, 0)

for p in parent:
	print(p+1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

parent = [-1] * n
depth = [-1] * n


def dfs(v, p, d):
    # print(v, p, d, parent, depth)
    if depth[v] != -1 and depth[v] > d:
        return
    parent[v] = p
    depth[v] = d
    for c in links[v]:
        dfs(c, v, d + 1)


dfs(root, -1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify

def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    isRoot = [True] * n
    for _ in range(n - 1 + m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        isRoot[b] = False

    for i in range(n):
        if isRoot[i]:
            root = i
            break
    INF = 10 ** 20
    stack = [(0, root, -1)]
    heapify(stack)
    height = [-INF] * n
    parent = [None] * n
    def search(stack):
        score, node, par = stack.pop()
        if -score > height[node]:
            height[node] = -score
            parent[node] = par
            for to in edges[node]:
                heappush(stack,(score - 1, to, node))

    while stack:
        search(stack)

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

main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
isRoot = [True] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    isRoot[b] = False

for i in range(n):
    if isRoot[i]:
        root = i
        break
INF = 10 ** 20
stack = [(root, -1, 0)]
height = [-INF] * n
parent = [None] * n
def search(stack):
    node, par, score = stack.pop()
    if score > height[node]:
        height[node] = score
        parent[node] = par
        for to in edges[node]:
            stack.append((to, node, score + 1))

while stack:
    search(stack)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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
    graph[a].append(b)
    in_count[b] += 1
root = in_count.index(0)

parent = [0] * n
dq = collections.deque()
dq.append((-1, root))
while dq:
    p, v = dq.popleft()
    parent[v] = p
    for nv in graph[v]:
        dq.append((v, nv))

for p in parent:
    print(p+1)

Submission status: Accepted

Solution code:

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
    
    # find root
    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')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
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()

Submission status: Accepted

Solution code:
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]:
        # 入次数を1減らす
        ks[v] -= 1
        # 0だった時、親が決まる。
        # 親が決まったとき、子を探す
        if ks[v] == 0:
            parents[v] = u
            q.appendleft(v) 

for p in parents:
    print(p+1)

Submission status: Accepted

Solution code:
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)
  
# https://ikatakos.com/pot/programming_algorithm/graph_theory/topological_sort
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)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
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))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
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))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
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))