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:
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for i in range(n - 1 + m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    inv[b - 1] += 1
for i in range(n):
    if inv[i] == 0:
        q = deque([i])
        break
ans = [0] * n
while q:
    d = q.popleft()
    for node in g[d]:
        ans[node] = d + 1
        q.append(node)
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

depth = [-1] * N

def dfs(v, d):
    depth[v] = max(depth[v], d)
    nd = d + 1
    for nv in to[v]:
        dfs(nv, nd)

root = -1
for v in range(N):
    if len(fr[v]) == 0:
        root = v
        break

dfs(root, 0)

vlist = [[] for _ in range(N)]
for v, d in enumerate(depth):
    vlist[d].append(v)

for v in range(N):
    d = depth[v]
    if d == 0:
        print(0)
        continue
    parent = set(vlist[d-1]) & set(fr[v])
    print(parent.pop()+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

depth = [-1] * N

def dfs(v, d):
    depth[v] = max(depth[v], d)
    nd = d + 1
    for nv in to[v]:
        dfs(nv, nd)

root = -1
for v in range(N):
    if len(fr[v]) == 0:
        root = v
        break

dfs(root, 0)

vlist = [[] for _ in range(N)]
for v, d in enumerate(depth):
    vlist[d].append(v)

for v in range(N):
    d = depth[v]
    if d == 0:
        print(0)
        continue
    parent = set(vlist[d-1]) & set(fr[v])
    print(parent.pop()+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    AB.append((A,B))
roots = [True]*N
for A, B in AB:
    roots[B] = False
for i in range(N):
    if roots[i]:
        root = i
        break

distance = [0]*N
parent = [-1]*N
pool = deque([(root,0)])
while pool:
    i, d = pool.popleft()
    for c in children[i]:
        if d+1 > distance[c]:
            distance[c] = d+1
            parent[c] = i
            pool.append((c,d+1))
for i in range(N):
    if parent[i] < 0:
        print(0)
    else:
        print(parent[i]+1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue


def main():
    n, m = map(int, input().split())

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

    WHITE = 0
    GRAY = 1
    BLACK = 2

    def bfs(s):
        q = Queue()
        color = [WHITE] * n
        d = [-1] * n
        p = [-2] * n

        q.put(s)
        color[s] = GRAY
        d[s] = 0
        p[s] = -1
        while not q.empty():
            u = q.get()
            color[u] = BLACK
            for v in g[u]:
                q.put(v)
                color[v] = GRAY
                d[v] = d[u] + 1
                p[v] = u

        if -2 in p:
            return False
        else:
            return p

    for i in range(n):
        p = bfs(i)
        if p:
            break

    for e in p:
        print(e + 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.pre = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				self.pre[i] = v
				self.Q.put(i)

#処理内容
def main():
	N, M = getlist()
	D = defaultdict(int)
	G = Graph()
	for i in range(N - 1 + M):
		A, B = getlist()
		G.add_edge(A - 1, B - 1)
		D[B - 1] += 1
	s = 0
	for i in range(N):
		if D[i] == 0:
			s = i
			break

	BF = BFS(G, s, N)
	ans = BF.pre
	for i in ans:
		if i == None:
			print(0)
		else:
			print(i + 1)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=deque([r])
while len(q)>0:
    u=q.popleft()
    for v in g[u]:
        ans[v-1]=u+1
        q.append(v-1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=[r]
while len(q)>0:
    u=q.pop()
    for v in g[u]:
        ans[v-1]=u+1
        q.append(v-1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    def dfs(u, ou=-1, d=0):
        if d < depth[u]: return
        parent[u] = ou + 1
        depth[u] = d
        for ku in to[u]:
            dfs(ku, u, d + 1)

    to = defaultdict(list)
    n, m = map(int, input().split())
    CntInDegree = [0] * n
    parent = [-1] * n
    depth = [-1] * n
    for _ in range(n + m - 1):
        a, b = map(int1, input().split())
        to[a].append(b)
        CntInDegree[b] += 1
    root = CntInDegree.index(0)
    # print(root)
    dfs(root)
    print(*parent, sep="\n")

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,M = II()
A,B = Line(N-1+M,2)

parent = [[] for _ in range(N)]
pt = [[] for _ in range(N)]

for i in range(N-1+M):
    parent[B[i]-1].append(A[i]-1)
    pt[A[i]-1].append(B[i]-1)

for i in range(N):
    if parent[i]==[]:
        root = i

ans = ['0']*N
q = [root]
while q:
    q_new = []
    for q1 in q:
        for v in pt[q1]:
            ans[v] = q1+1
            q_new.append(v)
    q = q_new

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

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()


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

graph = [[] for _ in range(N)]
depth = [0 for _ in range(N)]
parent_list = [[] for _ in range(N)]
parent = [-1 for _ in range(N)]

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

for i in range(N):
	if len(parent_list[i]) == 0:
		root = i
		break

que = deque([])
que.append(root)

while len(que) > 0:
	node = que.popleft()
	if len(graph[node]) > 0:
		for edge in graph[node]:
			depth[edge] = depth[node] + 1
			que.append(edge)

for i in range(N):
	parent_depth = -1
	parent_node = -1
	if len(parent_list[i]) > 0:
		for p in parent_list[i]:
			if depth[p] > parent_depth:
				parent_depth = depth[p]
				parent_node = p
		parent[i] = parent_node

#print(parent_list, depth)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m = map(int,input().split())
g = [set() for _ in range(n+1)]
gg = [0]*(n+1)
for _ in range(n-1+m):
    a,b = map(int,input().split())
    g[a].add(b)
    gg[b] = 1
p = [-1]*(n+1)
q = deque()
for i in range(1,n+1):
  if gg[i] == 0:
    p[i] = 0
    q.append(i)
    break
while q:
  v = q.popleft()
  for x in g[v]:
    q.append(x)
    p[x] = v
for x in p[1:]:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(node_num - 1 + edge_num)]

    parent_node = [0 for i in range(node_num + 1)]
    root_node = [1 for i in range(node_num + 1)]
    root_node[0] = 0
    graph_data = defaultdict(set)

    for i in range(node_num - 1 + edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        root_node[b] = 0

    root = -1
    for i in range(node_num + 1):
        if root_node[i]:
            root = i

    now_set = set()
    next_set = set()
    now_set.add(root)

    while len(now_set):
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                parent_node[next_node] = now_node
                next_set.add(next_node)
        now_set = next_set
        next_set = set()

    for i in range(1, node_num + 1):
        print(parent_node[i])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush, heappop

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

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
depth = [-1] * N
ans = [-1] * N

que = [(0, root, -1)]
while que:
    dp, now, pr = heappop(que)
    dp *= -1

    if depth[now] >= dp:
        continue
    depth[now] = dp
    ans[now] = pr + 1

    for ch in child[now]:
        if depth[ch] < dp + 1:
            heappush(que, (-(dp + 1), ch, now))

ans[root] = 0
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
depth = [-1] * N
ans = [-1] * N

st = deque([(root, root)])
while st:
    now, pr = st.popleft()
    if depth[now] >= depth[pr] + 1:
        continue
    depth[now] = depth[pr] + 1
    ans[now] = pr + 1
    for ch in child[now]:
        if depth[ch] >= depth[now] + 1:
            continue
        st.append((ch, now))

ans[root] = 0
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
depth = [-1] * N

st = deque([(root, root)])
while st:
    now, pr = st.popleft()
    if depth[now] >= depth[pr] + 1:
        continue
    depth[now] = depth[pr] + 1
    for ch in child[now]:
        if depth[ch] >= depth[now] + 1:
            continue
        st.append((ch, now))

ans = []
for i in range(N):
    if i == root:
        ans.append(0)
    else:
        for pr in parent[i]:
            if depth[i] == depth[pr] + 1:
                ans.append(pr + 1)
                break

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

parent = [[] for _ in range(N)]
child = [[] for _ in range(N)]

for _ in range(N - 1 + M):
    pr, ch = map(int, input().split())
    pr -= 1
    ch -= 1
    parent[ch].append(pr)
    child[pr].append(ch)

root = parent.index([])
depth = [-1] * N

st = deque([(root, root)])
while st:
    now, pr = st.pop()
    if depth[now] >= depth[pr] + 1:
        continue
    depth[now] = depth[pr] + 1
    for ch in child[now]:
        st.append((ch, now))

for i in range(N):
    if i == root:
        print(0)
    else:
        for pr in parent[i]:
            if depth[i] == depth[pr] + 1:
                print(pr + 1)
                break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [False] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] = True
# print (lst)

ans_lst = [[-1, 0] for _ in range(N)] #[親, 距離]を要素とするリスト
#根を求める = どこからも辺が伸びていないところ --> check_lst = Falseの場所
n = check_lst.index(False)
ans_lst[n][0] = -1
# print (n)

def dfs(i): #iからの経路を探す
    distance = ans_lst[i][1]
    for j in lst[i]:
        # print (j)
        if distance + 1 > ans_lst[j][1]:#距離が最長となるとき
            ans_lst[j][0] = i
            ans_lst[j][1] = distance + 1
            dfs(j)
    return 

dfs(n)
# print (ans_lst)

# print ('以下答え')
for i, d in ans_lst:
    print (i + 1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    Eb[b-1].append(a-1)

r = 0
while Eb[r]: r=Eb[r][0]

d = [-1]*N
d[r] = 0
q = [r]
while q:
    qq = []
    for i in q:
        di = d[i]
        for j in E[i]:
            if d[j]>=di+1:continue
            d[j] = di+1
            q.append(j)
    q = qq

p=[0]*N
for i in range(N):
    di = d[i]
    for j in Eb[i]:
        if d[j]==di-1:
            p[i] = j+1

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())

G=[]
C=[[] for i in range(n)]
B=[[] for i in range(n)]

for s in range(n+m-1):
    a,b=map(int,input().split())
    C[b-1].append(a)
    B[a-1].append(b)

root=C.index([])+1

S=[None for i in range(n)]

S[root-1]=0
now=root
N=[now]
NextN=[]

for i in range(n+m-1):
    
    for r in range(len(N)):
        #print("N:",N)
        now=N.pop(0)
        if len(B[now-1]) >0:
            for q in B[now-1]:
                S[q-1]=now
            NextN.extend(B[now-1])
            #print("S:",S)
    N.extend(NextN)
    NextN=[]
    if N == []:
        #print("END")
        break
        
    
for ans in S:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())

G=[]
C=[[] for i in range(n)]
B=[[] for i in range(n)]

for s in range(n+m-1):
    a,b=map(int,input().split())
    G.append([a,b])
    C[b-1].append(a)
    B[a-1].append(b)

root=C.index([])+1

S=[None for i in range(n)]

S[root-1]=0
now=root
N=[now]
NextN=[]
lev=1

for i in range(n+m-1):
    lev+=1
    
    for r in range(len(N)):
        #print("N:",N)
        now=N.pop(0)
        if len(B[now-1]) >0:
            for q in B[now-1]:
                S[q-1]=now
            NextN.extend(B[now-1])
            #print("S:",S)
    N.extend(NextN)
    NextN=[]
    
for ans in S:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# 入力
N, M = map(int, input().split())
A, B = zip(*(map(int, input().split()) for _ in range(N - 1 + M)))

# 各頂点の深さを求め、深さを利用して元の木を復元する
G = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G[a].add(b)
G_inv = [set() for _ in range(N + 1)]
for a, b in zip(A, B):
    G_inv[b].add(a)

r = next(i for i in range(1, N + 1) if not G_inv[i])

dp = [0 for _ in range(N + 1)]
q = deque([r])
while q:
    i = q.popleft()
    for j in G[i]:
        dp[j] = dp[i] + 1
        q.append(j)

ans = '\n'.join(
    str(max(G_inv[i], key=lambda j: dp[j], default=0))
    for i in range(1, N + 1)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(dict)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1][i]=b-1
    IN[b-1]|={i}
P=[0]*N
used=set()
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now].items():
        used|={b}
        if not (IN[nex]-used):
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(dict)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1][i]=b-1
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now].items():
        IN[nex].remove(b)
        if not IN[nex]:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        IN[nex].remove(b)
        if not IN[nex]:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        IN[nex].remove(b)
        if len(IN[nex])==0:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        if len(IN[nex])==1:
            start|={nex}
            P[nex]=now+1
        IN[nex]-={b}
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
P=[0]*N
while len(start)>0:
    now=start.pop()
    for b,nex in OUT[now]:
        if len(IN[nex])==1:
            start|={nex}
            P[nex]=now+1
        IN[nex]-={b}
    OUT[now]=set()
for p in P:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(set)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={(i,b-1)}
    IN[b-1]|={i}
L=[]
P=[0]*N
while len(start)>0:
    now=start.pop()
    L.append(now)
    for i in range(len(OUT[now])):
        b,nex = OUT[now].pop()
        if len(IN[nex])==1:
            start|={nex}
            P[nex]=now+1
        IN[nex]-={b}
for p in P:
    print(p)

Submission status: Time Limit Exceeded

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

ed = [ [] for i in range(N) ]
rv = [ [] for i in range(N) ]
mi = [ -10000000 ]*N
for a,b in li:
  ed[a].append(b)
  rv[b].append(a)

rvlen = [ len(it) for it in rv ]
rt = rvlen.index(0)
mi[rt]=0
st = [rt]
for i in range(10000000000000):
  _st = []
  for now in st:
    for it in ed[now]:
      mi[it] = max( mi[it],mi[now]+1)
    _st.extend(ed[now])
  st = _st
  if ( len(st) == 0 ):
    break

an = [0]*N
for i in range(N):
  d1 = mi[i]
  for it in rv[i]:
    if (d1-1 == mi[it]):
      an[i]=it+1
      break
print ( "\n".join(map(str,an)) )

Submission status: Time Limit Exceeded

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

ed = [ set() for i in range(N) ]
rv = [ set() for i in range(N) ]
mi = [ -1000000000 ]*N
for a,b in li:
  ed[a].add(b)
  rv[b].add(a)

rvlen = [ len(it) for it in rv ]
rt = rvlen.index(0)
mi[rt]=0
st = [rt]
for i in range(10000000):
  _st = []
  for now in st:
    for it in ed[now]:
      mi[it] = max( mi[it],mi[now]+1)
      _st.append(it)
  st = _st
  if ( len(st) == 0 ):
    break

an = [0]*N
for i in range(N):
  d1 = mi[i]
  for it in rv[i]:
    if (d1-1 == mi[it]):
      an[i]=it+1
      break
print ( "\n".join(map(str,an)) )

Submission status: Time Limit Exceeded

Solution code:
import collections

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

ans = [0] * (N + 1)
parent = [0] * (N + 1)
parent[0] = N+M
child = [[] for i in range(N+1)]
deq = collections.deque()

for i in range(N+M-1):
    p, c = map(int, input().split())
    parent[c] += 1
    child[p].append(c)
root = parent.index(min(parent))
deq.append(root)
while len(deq) > 0:
    v = deq.pop()
    if len(child[v]) > 0:
        for u in child[v]:
            deq.appendleft(u)
            ans[u] = v
for i in range(1,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import collections

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

ans = [0] * (N + 1)
depth = [0] * (N + 1)
parent = [[] for i in range(N+1)]
child = [[] for i in range(N+1)]
deq = collections.deque()

for i in range(N+M-1):
    p, c = map(int, input().split())
    parent[c].append(p)
    child[p].append(c)
for i in range(1, N+M-1):
    if len(parent[i]) == 0:
        deq.append(i)
        break
while len(deq) > 0:
    v = deq.pop()
    if len(child[v]) > 0:
        for u in child[v]:
            deq.appendleft(u)
            ans[u] = v
for i in range(1,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,m = (int(i) for i in input().split())
x,y = [[] for i in range(n+1)],[1]*(n+1)
for i in range(n+m-1):
    a,b = (int(i) for i in input().split())
    x[a].append(b)
    y[b] = 0
for i in range(1,n+1):
    if y[i]: break
r,ans,q = i,[0]*(n+1),[i]
while q:
    p = q.pop()
    for i in x[p]:
        q.append(i)
        ans[i] = p
for i in ans[1:]: print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
# import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

t_index = {i: [] for i in range(max(inflow.values()) + 1)}
for edge, count in inflow.items():
    t_index[count].append(edge)

sorted_edges = []
while len(sorted_edges) < N:
    par = t_index[0].pop()
    sorted_edges.append(par)
    for chi in child[par]:
        t_index[inflow[chi]].remove(chi)
        inflow[chi] -= 1
        t_index[inflow[chi]].append(chi)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        par = -1
        for p in parent[i]:
            par = max(par, sorted_edges.index(p))
        print(sorted_edges[par])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

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

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

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

while cnt < n:
    ptank = ctank
    ctank = deque()
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    for i in clist:
        used[i-1] = 1
    clist = list()
    

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from copy import deepcopy

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

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

rws = deepcopy(ws)

#print(vs)
#print(ws)

# topological sort

L = []
S = [i for i in range(1, N + 1) if not ws[i]]

while S:
    n = S.pop()
    L.append(n)
    for m in vs[n]:
        rws[m].remove(n)
        if not rws[m]:
            S.append(m)

#print(S)
#print(L)

nrank = {}

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

#print(nrank)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, M = list(map(int, input().split()))
  L = {}
  D = [[0, i] for i in range(N+1)]

  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    if Data[0] in L:
      L[Data[0]].append(Data[1])
    else:
      L[Data[0]] = [Data[1]]
    D[Data[1]][0] += 1

  for i in range(1, N+1):
    if D[i][0] == 0:
     s = D[i][1]
     break

  P = [[0, 0] for i in range(N + 1)]
  S = []
  t = L[s]
  for i in t:
    S.append(i)
    P[i] = [1, s]

  while True:
    if len(S) == 0:
      break
    j = S.pop()
    if j not in L:
      continue
    t = L[j]
    for i in t:
      if P[i][0] != 0:
        if P[i][0] < P[j][0] + 1:
          P[i] = [P[j][0] + 1, j]
          S.append(i)
      else:
        P[i] = [P[j][0] + 1, j]
        S.append(i)
  for i in P[1:]:
    print(i[1])

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def is_input(node, path):
    for i in range(len(path)):
        if path[i][node]:
            return True
    return False


def topological_sort(path):
    S = []
    for i, input_nodes in enumerate(input_nodes_list):
        if len(input_nodes_list) == 0:
            S.append(i)
    path = path.copy()
    for i in range(len(path)):
        flag = True
        for j in range(len(path)):
            if path[j][i]:
                flag = False
                input_nodes_list[i].append(j)
        if flag:
            S.append(i)
    res = []
    while len(S) > 0:
        now = S.pop()
        res.append(now)
        for i, f in enumerate(path[now]):
            if f:
                path[now][i] = False
                if not is_input(i, path):
                    S.append(i)
    return res


N, M = map(int, input().split(" "))
path = np.array([[False for i in range(N)] for i in range(N)])
input_nodes_list = [[] for i in range(N)]

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

sorted_nodes = topological_sort(path)
dict_sorted_nodes = {}
for i, v in enumerate(sorted_nodes):
    dict_sorted_nodes[v] = i


for input_nodes in input_nodes_list:
    if len(input_nodes) == 0:
        print(0)
        continue
    if len(input_nodes) == 1:
        print(input_nodes[0]+1)
        continue
    temp_i = 0
    for j in input_nodes:
        temp_i = max(temp_i, dict_sorted_nodes[j])

    print(sorted_nodes[temp_i]+1)