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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
s = [set() for i in range(n)]
c = [set() for i in range(n)]
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  s[a].add(b)
  c[a].add(b)
  
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc
                
    def update(self, k, r):
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k*2], self.seg[k*2+1])

S = segment_(n,set(),lambda a, b: a|b)
for i,ci in enumerate(c):
  S.update(i,ci)
  
p = set([int(i) for i in range(n)])
ans = [0]*n
root = deque()
root.append(-1)
cnt = 0
l = [1]*n

while root:
  if cnt == n:
    break
  now = root.popleft()
  if now >= 0:
    S.update(now,set())
    l[now] -= 1
  child = list(p-S.seg[1])
  for nex in child:
    cnt += 1
    ans[nex] = now+1
    root.append(nex)
    p.remove(nex)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
s = [set() for i in range(n)]
c = [set() for i in range(n)]
for i in range(m+n-1):
  a,b = map(int,readline().split())
  a -= 1
  b -= 1
  s[a].add(b)
  c[a].add(b)
  
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc
                
    def update(self, k, r):
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k*2], self.seg[k*2+1])

S = segment_(n,set(),lambda a, b: a|b)
for i,ci in enumerate(c):
  S.update(i,ci)
  
p = set([int(i) for i in range(n)])
ans = [0]*n
root = deque()
root.append(-1)
cnt = 0
l = [1]*n

while root:
  if cnt == n:
    break
  now = root.popleft()
  if now >= 0:
    S.update(now,set())
    l[now] -= 1
  child = list(p-S.seg[1])
  for nex in child:
    cnt += 1
    ans[nex] = now+1
    root.append(nex)
    p.remove(nex)
  if now >= 0 and l[now] != 0:
    S.update(now,s[now])
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    書き足した辺は，子孫に対してのものなのでいわゆるショートかっと．
    後から同じ頂点にたどり着いた場合，そちらを優先する？
    """
    
    mod=10**9+7
    N,M=MI()
    fro=[[]for _ in range(N)]
    to=[[]for _ in range(N)]
    
    for _ in range(N+M-1):
        a,b=MI()
        a-=1
        b-=1
        fro[b].append(a)
        to[a].append(b)
        
    root=0
    for i in range(N):
        if len(fro[i])==0:
            root=i
            break
        
    P=[-1]*N
    
    
    import queue
    q=queue.Queue()
    q.put(root)
    
    while not q.empty():
        v=q.get()
        for nv in to[v]:
            q.put(nv)
            P[nv]=v
                
    for i in range(N):
        print(P[i]+1)
    
        

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n, m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
pps = [set() for _ in range(n)]
for i in range(n-1+m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    pps[b].add(a)

for i,s in enumerate(pps):
    if not s:
        r = i
        
ps = [None] * n    
def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None or seen[v]<d+1:
                seen[v] = d + 1
                q.appendleft(v)
                ps[v] = u+1
    return seen

ds = bfs(r)
ps[r] = 0
write("\n".join(map(str, ps)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(N-1+M)]
graph = [[] for _ in range(N)]
d_in = [0]*N
for a, b in AB:
	a, b = a-1, b-1
	graph[a].append(b)
	d_in[b] += 1

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

ans = [None]*N
ans[root] = 0
q = deque([root])
while q:
	n = q.popleft()
	for node in graph[n]:
		ans[node] = n+1
		q.append(node)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
    else:
        nex = []
    for n in nex:
        parent[n-1] = p
        que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

edges = {}
root = set([i+1 for i in range(n)])
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    root.discard(b)

# print(root.pop())

root = root.pop()
que = deque()
que.append(root)
parent = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
    else:
        nex = []
    for n in nex:
        parent[n-1] = p
        que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for _ 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:
        root = i
        break
d = [0] * n
s = [root]
while s:
    p = s.pop()
    for node in g[p]:
        d[node] = max(d[node], d[p] + 1)
        s.append(node)
ans = [0] * n
for i in range(n):
    for node in g[i]:
        if d[node] == d[i] + 1:
            ans[node] = i + 1
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# 有効グラフ上で、近道に当たる点はすべて余計な辺
# ある点に入ってくる最も距離が長い辺のみが有効となる
# 一番距離が長い人版ダイクストラやってみる
# 入力のあった頂点を記録することで、入力の無かった頂点を根とみなせる

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
grandparent = set(range(N))
for i in range(N - 1 + M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  grandparent -= {b - 1}

start = list(grandparent)[0]
import heapq

# 距離, 頂点, 親
q = [(0, start, -1)]
heapq.heapify(q)

# ans[頂点] = (到達コスト,親)
ans = [(-1, -1) for i in range(N)]
while q:
  dist, v, parent = heapq.heappop(q)
  dist = -dist
  if ans[v][0] >= dist:
    continue
  ans[v] = (dist, parent)
  for child in G[v]:
    heapq.heappush(q,(-(dist + 1), child, v))
    
for a in ans:
  print(a[1] + 1)

Submission status: Time Limit Exceeded

Solution code:
# 有効グラフ上で、近道に当たる点はすべて余計な辺
# ある点に入ってくる最も距離が長い辺のみが有効となる
# DFSで、あとから入ってきたときにその親を記録すればよいのでは。
# 最後に残ったものを出力する
# 入力のあった頂点を記録することで、入力の無かった頂点を根とみなせる

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
grandparent = set(range(N))
for i in range(N - 1 + M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  grandparent -= {b - 1}

start = list(grandparent)[0]
from collections import deque

D = -1000
ans = [D for i in range(N)]

# 頂点、親
q = deque([[start, -1]])
while q:
  v, parent = q.popleft()
  ans[v] = parent
  for child in G[v]:
    q.append([child, v])
    
for a in ans:
  print(a + 1)

Submission status: Time Limit Exceeded

Solution code:
# 有効グラフ上で、近道に当たる点はすべて余計な辺
# ある点に入ってくる最も距離が長い辺のみが有効となる
# ある頂点に対して入ってきた辺の(cost, 入力元)を持っておき、
# さらに距離の長い辺がやってきたら(cost, 入力元)で置き換える
# 最後に残ったものを出力する
# 入力のあった頂点を記録することで、入力の無かった頂点を根とみなせる

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
grandparent = set(range(N))
for i in range(N - 1 + M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  grandparent -= {b - 1}

start = list(grandparent)[0]
from collections import deque

longest = [(-1,-1) for i in range(N)]
# longest[頂点] =  (コスト, 入力元)
longest[start] = (0, -1)

# 頂点, コスト, 入力元
q = deque([(start, 0, -1)])
while q:
  v, dist, parent = q.popleft()
  if longest[v][0] > dist:
    continue
  longest[v] = (dist, parent)
  for child in G[v]:
    q.append((child, dist + 1, v))
  
for g in longest:
  print(g[1] + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,M=map(int,input().split())
s=[set() for i in range(N)]
t=[1]*N
for i in range(N+M-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].add(b)
    t[b]=0
k=t.index(1)
l=[-1]*N
b={k}
while b:
    a=set()
    for i in b:
        a|=s[i]
        for j in s[i]:
            l[j]=i
    b=a
for i in l:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,M=map(int,input().split())
s=[[]for i in range(N)]
t=[1]*N
for i in range(N+M-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    t[b]=0
k=t.index(1)
l0=[0]*N
l1=[0]*N
def hu(c,n):
    for i in s[n]:
        if l0[i]<c:
            l0[i]=c
            l1[i]=n+1
            hu(c+1,i)
hu(1,k)
print(*l1,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,M=map(int,input().split())
s=[[]for i in range(N)]
t=[1]*N
for i in range(N+M-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    t[b]=0
k=t.index(1)
def hu(c,n):
    for i in s[n]:
        if l[i][0]<c:
            l[i]=[c,n]
            hu(c+1,i)
l=[[0,-1]for i in range(N)]
l[k]=[0,-1]
hu(1,k)
for i in range(N):
    print(l[i][1]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def main():
    n, m = map(int, sys.stdin.readline().split())

    to = [[] for _ in range(n + 1)]
    a_set = {x for x in range(1, n + 1)}
    b_set = set()
    for _ in range(n - 1 + m):
        a, b = map(int, sys.stdin.readline().split())
        to[a].append(b)
        b_set.add(b)
    root = (a_set - b_set).pop()
    dist = [0] * (n + 1)
    pre = [0] * (n + 1)
    que = deque([])
    que.append(root)

    while que:
        p = que.popleft()
        for i in to[p]:
            if dist[i] < dist[p] + 1:
                dist[i] = dist[p] + 1
                pre[i] = p
                que.append(i)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    from collections import deque
    input = sys.stdin.readline
    n,m = map(int,input().split())
    edgein = [[] for i in range(n)]
    edgeout = [[] for i in range(n)]
    edgecnt=[0]*n
    rootnum=0
    for i in range(n+m-1):
        a,b= map(int,input().split())
        edgein[b-1].append(a-1)
        edgeout[a-1].append(b-1)
    for i in range(n):
        edgecnt[i]=len(edgein[i])
        if edgecnt[i]==0:
            rootnum=i
    chkedge=deque()
    chkedge.append(rootnum)
    while chkedge:
        chk=chkedge.popleft()
        for i in edgeout[chk]:
            edgecnt[i]=max(edgecnt[i],edgecnt[chk]+1)
            chkedge.append(i)
    for i in range(n):
        chk=edgecnt[i]
        if not edgein[i]:
            print(0)
        for j in edgein[i]:
            if edgecnt[j]==chk-1:
                print(j+1)
                break

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

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

in_out = [[[], []] for i in range(N)]

for edge in edges:
    x, y = edge
    in_out[x-1][1].append(y)
    in_out[y-1][0].append(x)

for i in range(N):
    if len(in_out[i][0]) == 0:
        start = i+1
        break

edge_dict = {}
que = deque([[0, start]])
def bfs(past, now):
    edge_dict[now] = past
    try: 
        x, y = que.popleft()
        for node in in_out[y-1][1]:
            que.append([y, node])
        bfs(x, y)
    except IndexError:
        pass
    

bfs(0, start)
dic = sorted(edge_dict.items())
for edge in dic:
    print(edge[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
s=set()
edge=[[] for _ in range(n)]
for _ in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    s.add(b)
for i in range(n):
    if i not in s:
        root=i
        break
def bfs(root):
    q=deque([root])
    visited=[(0,0) for _ in range(n)]
    visited[root]=(0,-1)
    while q:
        p=q.popleft()
        dp,pp=visited[p]
        for c in edge[p]:
            dc,cp=visited[c]
            if dc<dp+1:
                visited[c]=(dp+1,p)
                q.append(c)
    return visited
visited=bfs(root)
#print(visited)
for d,i in visited:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
s=set()
edge=[[] for _ in range(n)]
for _ in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    s.add(b)
for i in range(n):
    if i not in s:
        root=i
        break
def bfs(root):
    q=deque([root])
    visited=[[0,0] for _ in range(n)]
    visited[root]=[0,-1]
    while q:
        p=q.popleft()
        dp,pp=visited[p]
        for c in edge[p]:
            dc,cp=visited[c]
            if dc<dp+1:
                visited[c]=[dp+1,p]
                q.append(c)
    return visited
visited=bfs(root)
#print(visited)
for d,i in visited:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, v: int, p: int, depth: int, dd: {}, dq):
    dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 探索キューに追加
        dq.append((next_v, v, depth+1))


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

    children = set()
    g = {}
    # parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        # dic_b = parent_g.setdefault(b - 1, [])
        # dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}

    dq = collections.deque()
    dq.append((root, parent, depth))
    while len(dq) > 0:
        t, p, d = dq.popleft()
        bfs(g, t, p, d, dd, dq)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, v: int, p: int, depth: int, dd: {}):
    d_v = dd.setdefault(v, (p, depth))
    if depth > d_v[1]:
        dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 再帰的に探索
        bfs(g, next_v, v, depth + 1, dd)


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

    children = set()
    g = {}
    # parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        # dic_b = parent_g.setdefault(b - 1, [])
        # dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}
    bfs(g, root, parent, depth, dd)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, v: int, p: int, depth: int, dd: {}):
    d_v = dd.setdefault(v, [])
    d_v.append((p, depth))

    if v in g.keys():
        for next_v in g[v]:
            # next_v が親だったらスルー
            if next_v == p:
                continue
            # 再帰的に探索
            bfs(g, next_v, v, depth + 1, dd)


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

    children = set()
    g = {}
    parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        dic_b = parent_g.setdefault(b - 1, [])
        dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}
    bfs(g, root, parent, depth, dd)

    for i in range(n):
        v = dd[i]
        if len(v) == 1:
            print(v[0][0]+1)
            continue

        v.sort(key=lambda x: x[1], reverse=True)
        print(v[0][0]+1)



main()

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(v) for v in input().split()]
ad_list = [[] for _ in range (N+1)]
ad_num = [0 for _ in range(N)]
topo = []

for _ in range(N-1+M):
    l,r = [int(v) for v in input().split()]
    ad_list[l].append(r)
    ad_num[r-1] += 1

for i in range(1,N+1):
    if ad_num[i-1] == 0:
        topo.append(i)
queue = topo[:]
topo = [[0,topo[0]]]
while queue:
    n1 = queue.pop(0)
    for n2 in ad_list[n1]:
        ad_num[n2-1] -= 1
        if ad_num[n2-1] == 0:
            topo.append([n1,n2])
            queue.append(n2)
topo.sort(key=lambda x:x[1])
for i,v in topo:
    print(i)
#  visited = [False for _ in range(N)]

#  ans = 0
#  path_len = 0
#  def dfs(node,cnt=1):
    #  global ans
    #  if visited[node-1]: return 0
    #  visited[node-1] = True
    #  ans = max(ans,cnt)
    #  for n in ad_list[node]:
        #  dfs(n,cnt+1)

#  for n in range(1,N+1):
    #  dfs(n)
#  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    def dfs(i,j):
        for e in edg[i]:
            if ans[e][1] >= j + 1:
                continue
            dfs(e, j + 1)
            ans[e] = [i, j + 1]
    n, m = LI()
    edg = [[] for i in range(n)]
    rev_edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
        rev_edg[b].append(a)
    for i, e in enumerate(rev_edg):
        if len(e):
            continue
        root = i
        break
    ans = [[-1, 0]] * n
    dfs(root, 0)
    print("\n".join(map(str, map(lambda x: x[0] + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i,e in enumerate(edg):
        if len(e) == 1:
            ans[e[0]] = i
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if d[e]:
                    ans[e] = -1
                    edg[i].remove(e)
                    d[e] = 0
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if d[e]:
                    ans[e] = -1
                    edg[i].remove(e)
                    d[e] = 0
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        for t in edg[i]:
            if ans[t] == -1:
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                ans[e] = p
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}

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

    root = (set(range(1, N+1))-used).pop()

    q = deque([(root, 0, 0)])
    parents = [0] * N
    dist = [0] * (N+1)

    while q:
        s, r, x = q.popleft()
        if x>dist[s] or r==0:
            dist[s] = x
            parents[s-1] = r
        else:
            continue
        for t in d[s]:
            q.append((t, s, x+1))

    for i in parents:
        print(i)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}

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

    root = (set(range(1, N+1))-used).pop()

    q = [(root, 0, 0)]
    parents = [0] * N
    dist = [0] * (N+1)

    while q:
        s, r, x = q.pop()
        if x>dist[s] or r==0:
            dist[s] = x
            parents[s-1] = r
        else:
            continue
        for t in d[s]:
            q.append((t, s, x+1))

    for i in parents:
        print(i)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    e = {i:[] for i in range(1, N+1)}

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

    root = [k for k,v in e.items() if not v][0]
    dist = [0] * (N+1)

    q = [(root, 0, 0)]
    parents = [0] * (N+1)

    while q:
        s, r, x = q.pop()
        if x>dist[s] or r==0:
            dist[s] = x
            parents[s] = r
        else:
            continue
        for t in d[s]:
            q.append((t, s, x+1))

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    e = {i:[] for i in range(1, N+1)}

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

    root = [k for k,v in e.items() if not v][0]
    dist = [0] * (N+1)

    q = [(root, 0, 0)]
    parents = [0] * (N+1)

    while q:
        s, r, x = q.pop()
        if x>dist[s]:
            dist[s] = x
            parents[s] = r
        for t in d[s]:
            q.append((t, s, x+1))

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

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

root = [k for k,v in e.items() if not v][0]
dist = [0] * (N+1)

q = [(root, 0, 0)]
parents = [0] * (N+1)

while q:
    s, r, x = q.pop()
    if x>dist[s]:
        dist[s] = x
        parents[s] = r
    for t in d[s]:
        q.append((t, s, x+1))

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