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 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 = []
    path = path.copy()
    for i in range(len(path[0])):
        if any(path[:, i]):
            pass
        else:
            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)])


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

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


for line in path.T:
    input_nodes = []
    for j, f in enumerate(line):
        if f:
            input_nodes.append(j)

    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)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import numpy as np
import bisect


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


def topological_sort(path):
    S = []
    path = np.array(path)
    for i in range(len(path[0])):
        if any(path[:, i]):
            pass
        else:
            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 = [[False for i in range(N)] for i in range(N)]


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

sorted_nodes = topological_sort(path)

input_nodes_list = [[] for i in range(N)]
for i, line in enumerate(path):
    temp = []
    for j, f in enumerate(line):
        if f:
            input_nodes_list[j].append(i)
ans = []
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 i in input_nodes:
        temp_i = max(temp_i, dict_sorted_nodes[i])

    print(sorted_nodes[temp_i]+1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
fromto=[list(map(int,input().split()))for _ in range(n+m-1)]
m += n-1
fr = [[]for _ in range(n+1)]
to = [0]*(n+1)
ans = [0]*(n+1)
for f,t in fromto:
    fr[f].append(t)
    to[t]+=1
for i in range(1,n+1):
    if to[i] is 0:
        root = i
q=[root]
while q:
    now = q.pop(0)
    for nex in fr[now]:
        to[nex] -= 1
        if to[nex] is 0:
            ans[nex] = now
            q.append(nex)

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

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def topological_sort(graph: dict) -> list:
    stack = deque([])
    visited = set()
    not_leaf = set(graph.keys())
    sort_list = []

    for i in graph.keys():
        if i in visited:
            continue
        stack.append(i)

        while stack:
            v = stack[-1]
            if v not in not_leaf:
                sort_list.append(stack.pop())
                visited.add(v)
                continue

            for next in graph[v]:
                if next not in visited:
                    stack.append(next)
                    break
            else:
                sort_list.append(stack.pop())
                visited.add(v)

    return sort_list[::-1]


n, m = LI()
T = defaultdict(list)

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

ts_list = topological_sort(T)


tree = defaultdict(int)
tree[ts_list[0]] = 0
queue = deque([ts_list[0]])
while queue:
    v = queue.popleft()
    for next in T[v]:
        tree[next] = v
        queue.append(next)

print(*tree.values(), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
oya=[set() for i in range(n)]
ko=[set() for i in range(n)]
rank=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    ko[a-1].add(b-1)
    oya[b-1].add(a-1)
for s in range(n):
    if not oya[s]:break
q={s}
ans=[0]*n
while q:
    now=q.pop()
    for i in ko[now]:
        if oya[now]:continue
        oya[i].remove(now)
        if not oya[i]:
            ans[i]=now+1
            q|=ko[now]
for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import queue

n, m = map(int, input().split())
e = []
p = {i+1:set() for i in range(n)}

for i in range(n-1+m):
    a, b = map(int, input().split())
    e.append((a, b))
    p[b].add(a)

for c, ps in p.items():

    if len(ps) == 0:
        ps.add(0)
        continue
    elif len(ps) == 1:
        continue

    tp = set(ps)
    for parent in tp:
        ps.remove(parent)

        q = queue.Queue()
        q.put(c)
        visited = set()
        isExist = False
        while not q.empty():
            vq = q.get()
            visited.add(vq)
            if vq == parent:
                isExist = True
                break
            elif vq == 0:
                break
            for ttp in p[vq]:
                if not ttp in visited:
                    q.put(ttp)

        if not isExist:
            ps.add(parent)

for i in range(n):
    print(list(p[i+1])[0])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())

# 隣接リスト
A = [[] for _ in range(N)]
# 根
root = -1
R = [True]*N

for i in range(N-1+M):
    a,b = map(int,input().split())
    # a -> b
    A[a-1].append(b-1)
    # a -> b のため、bには親がいる
    R[b-1] = False

# 親判定
for i in range(N):
    if R[i]:
        root = i
        break

# 出力すべき木の親を確定させる
P = [-1]*N
P[root] = -1

from collections import deque
Q = deque([root])
while Q!=deque([]):
    tmpQ = deque([])
    for q in Q:
        for i in A[q]:
            # 親の更新
            P[i] = q
            # 自身をtmpQに
            tmpQ.append(i)
    Q = tmpQ

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
num_list=[]
for i in range(0,N):
    num_list.append([])
a=0
b=0
for i in range(0,N+M-1):
    a,b=map(int, input().split())
    #aが親bが子
    num_list[b-1].append(a-1)
count=0
tmp=[]
tmp_pre=[]
ans=[0]*N
while count<N:
    for i in range(0,N):
        if(count==0):
            if(num_list[i]==[]):
                count+=1
                tmp_pre.append(i)
                num_list[i].append(-1)
                break
        for j in tmp:
            if(j in num_list[i]):
                num_list[i].remove(j)
                if(num_list[i]==[]):
                    ans[i]=j+1
                    count+=1
                    tmp_pre.append(i)
                    num_list[i].append(-1)
    tmp=tmp_pre
    tmp_pre=[]

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())

# 隣接リスト
A = [[] for _ in range(N)]
# 根
root = -1
R = [True]*N

for i in range(N-1+M):
    a,b = map(int,input().split())
    # a -> b
    A[a-1].append(b-1)
    # a -> b のため、bには親がいる
    R[b-1] = False

# 親判定
for i in range(N):
    if R[i]:
        root = i
        break

# 出力すべき木の親を確定させる
P = [-1]*N
P[root] = -1

from collections import deque
Q = deque([root])
while Q!=[]:
    tmpQ = deque([])
    for q in Q:
        for i in A[q]:
            # 親の更新
            P[i] = q
            # 自身をtmpQに
            tmpQ.append(i)
    Q = tmpQ

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())

# 隣接リスト
A = [[] for _ in range(N)]
# 根
root = -1
R = [True]*N

for i in range(N-1+M):
    a,b = map(int,input().split())
    # a -> b
    A[a-1].append(b-1)
    # a -> b のため、bには親がいる
    R[b-1] = False

# 親判定
for i in range(N):
    if R[i]:
        root = i
        break

# 出力すべき木の親を確定させる
P = [-1]*N
P[root] = -1

Q = [root]
while Q!=[]:
    tmpQ = []
    for q in Q:
        for i in A[q]:
            # 親の更新
            P[i] = q
            # 自身をtmpQに
            tmpQ.append(i)
    Q = tmpQ

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

Submission status: Time Limit Exceeded

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

# 隣接リスト
A = [[] for _ in range(N)]

# 根
root = -1
R = [True]*N
for (a,b) in AB:
    R[b-1] = False
    A[a-1].append(b-1)

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

# 親
P = [-1]*N
P[root] = -1

Q = [root]
while Q!=[]:
    tmpQ = []
    for q in Q:
        for i in A[q]:
            # 親の更新
            P[i] = q
            # 自身をtmpQに
            tmpQ.append(i)
    Q = tmpQ

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
n,m = map(int,input().split())

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

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1
used2 = [0]*n
used2[root]=1
#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            used2[e]=1
            res[e]=z+1
            tank2.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
while c != n:
    tank = tank2
    tank2 = deque([])
    used = copy.deepcopy(used2)
    while len(tank)!=0:
        f(tank.popleft())
    c += len(tank2)
    
for i in range(n):
    print(res[i])

Submission status: Time Limit Exceeded

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

edgeList = [list(map(int, input().split())) for _ in range(n+m-1)]
d    = {i:0 for i in range(1, n+1)}
g    = {i:[]    for i in range(1, n+1)}
used = {i:False for i in range(1, n+1)}

for p in edgeList:
    d[p[1]] += 1
    used[p[1]] = True
    g[p[0]].append(p[1])

root = -1
for k in used:
    if used[k] == False:
        root = k
        break
        
edge = {}
q = []
q.append(root)

while(len(q)>0):
    cur = q.pop(0)
    for node in g[cur]:
        if d[node] > 1:
            d[node] -= 1
        else:
            edge[node] = cur
            q.append(node)

for i in range(1, n+1):
    print(0) if i == root else print(edge[i])

Submission status: Time Limit Exceeded

Solution code:
def dfs(cur, edge):
    for node in g[cur]:
        if len(d[cur]) > 1:
            d[node].remove(cur)
        else:
            edge[node] = cur
            dfs(node, edge)
    
n, m     = map(int, input().split())

edgeList = [list(map(int, input().split())) for _ in range(n+m-1)]
d    = {i:set() for i in range(1, n+1)}
g    = {i:[]    for i in range(1, n+1)}
used = {i:False for i in range(1, n+1)}

for p in edgeList:
    d[p[1]].add(p[0])
    used[p[1]] = True
    g[p[0]].append(p[1])

root = -1
for k in used:
    if used[k] == False:
        root = k
        break
        
edge = {}
q = []
q.append(root)

while(len(q)>0):
    cur = q.pop(0)
    for node in g[cur]:
        if len(d[node]) > 1:
            d[node].remove(cur)
        else:
            edge[node] = cur
            q.append(node)

for i in range(1, n+1):
    print(0) if i == root else print(edge[i])

Submission status: Time Limit Exceeded

Solution code:
def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    ret = []
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


def main():
    N, M = map(int, input().split())
    E_in = [[] for _ in range(N)]
    E_from = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E_from[a].append(b)
        E_in[b].append(a)

    top_sort = topological_sort(N, E_in, E_from)

    # こっからを改善
    parent = [0]*N
    for i in range(N):
        current = top_sort[i]
        for j in reversed(top_sort[:i]):
            if current in E_from[j]:
                parent[current] = j+1
                break

    ans = '\n'.join(map(str, parent))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    ret = []
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


def main():
    N, M = map(int, input().split())
    E_in = [[] for _ in range(N)]
    E_from = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E_from[a].append(b)
        E_in[b].append(a)

    top_sort = topological_sort(N, E_in, E_from)
    parent = [0]*N
    for i in range(N):
        current = top_sort[i]
        for j in reversed(top_sort[:i]):
            if current in E_from[j]:
                parent[current] = j+1
                break

    ans = '\n'.join(map(str, parent))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def topological_sort(V, adj):
    '''
    V:N(node)
    adj:adjacency matrix
    '''

    # count num of pointed nodes for each nodes
    cnt = [0]*V
    for a in adj:
        for j in a:
            cnt[j] += 1
    "set of nodes which is not pointed from other"
    Q = []
    for i in range(V):
        if cnt[i] == 0:
            Q.append(i)

    ret = []
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in adj[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    #print("ret->", ','.join(map(lambda x: str(x+1), ret)))
    return ret


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)

    top_sort = topological_sort(N, adj)
    parent = [-1]*N
    for i in range(N):
        current = top_sort[i]
        par_cand = top_sort[:i]
        #print("par_i_cand->", par_cand)
        if not par_cand:
            parent[current] = 0
        else:
            for j in reversed(par_cand):
                if current in adj[j]:
                    parent[current] = j+1
                    break

    ans = '\n'.join(map(str, parent))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
v,n=map(int,input().split())
n+=v-1
es=[[int(x)for x in input().split()]for _ in range(n)]
outs={}
ins={}
for v1,v2 in es:
    outs[v1]=outs.get(v1,[])+[v2]
    ins[v2]=ins.get(v2,0)+1
q=deque(v1 for v1 in range(v)if not ins.get(v1,0))
res=[]
p=[0]*-~v
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in outs.get(v1,[]):
        ins[v2]-=1
        if ins[v2]==0:
            q.append(v2)
            p[v2]=v1
for t in p[1:]:print(t)

Submission status: Time Limit Exceeded

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

start = []
end = []
count = [0]*N
repeat_list = []
for i in range(N+M-1):
    start.append(data[i][0])
    end.append(data[i][1])
    count[data[i][1]-1] += 1
    repeat_list.append(i)

answer = [0]*N

while len(repeat_list) > 0:
    n = count.index(0)
    delete = []

    for i in repeat_list:
        if start[i] == n+1:
            count[end[i]-1] -= 1
            answer[end[i]-1] = n+1
            delete.append(i)
    repeat_list = list(set(repeat_list) - set(delete))
    count[n] = -1

for i in answer:
    print(i)

Submission status: Time Limit Exceeded

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





top_sort = []

S = [data[i][1] for i in range(N+M-1)]
S = list(set(range(1, N+1)) - set(S))   # 入力辺を持たないノードの集合
no = range(N+M-1)   # まだ残っている辺の番号

answer = [0]*N

while len(S) > 0:
    n = S.pop(0)
    top_sort.append(n)

    for i in range(N+M-1):
        if data[i][0] == n:
            no = list(set(no) - set([i]))
            answer[data[i][1]-1] = n
    S = [data[i][1] for i in no]
    S = list(set(range(1, N+1)) - set(S) - set(top_sort))

# print(top_sort)



for i in answer:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, M, AB):

    in_n = [0] * (N+1)
    g = defaultdict(list)
    rg = defaultdict(list)
    for a, b in AB:
        in_n[b] += 1
        g[a].append(b)
        rg[b].append(a)

    r = []
    for i, n in enumerate(in_n):
        if i != 0 and n == 0:
            r.append(i)

    sv = []
    while r:
        u = r.pop()
        sv.append(u)
        for v in g[u]:
            in_n[v] -= 1
            if in_n[v] == 0:
                r.append(v)

    for i in range(1, N+1):
        mi = 0
        if len(rg[i]) == 0:
            print(0)
        else:
            for j in rg[i]:
                mi = max(mi, sv.index(j))
            print(sv[mi])
    return


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(N+M-1)]
    slv(N, M, AB)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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





top_sort = []

S = [data[i][1] for i in range(N+M-1)]
S = list(set(range(1, N+1)) - set(S))   # 入力辺を持たないノードの集合
no = range(N+M-1)   # まだ残っている辺の番号

while len(S) > 0:
    n = S.pop(0)
    top_sort.append(n)

    for i in range(N+M-1):
        if data[i][0] == n:
            no = list(set(no) - set([i]))
    S = [data[i][1] for i in no]
    S = list(set(range(1, N+1)) - set(S) - set(top_sort))

# print(top_sort)


answer = [0]*N

for i in top_sort[1:]:
    index = 0
    for j in range(N+M-1):
        if data[j][1] == i:
            index = max(index, top_sort.index(data[j][0]))
    answer[i-1] = top_sort[index]

for i in answer:
    print(i)

Submission status: Time Limit Exceeded

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

seta = set()
setall = set(i for i in range(1, n + 1))
way = {}
for i in range(n + m - 1):
    seta.add(ab[i][1])
    if ab[i][0] in way:
        way[ab[i][0]].append(ab[i][1])
    else:
        way[ab[i][0]] = [ab[i][1]]
top = (setall - seta).pop()
cld = {i:top for i in way[top]}
nexta = way[top]
nowp = top
while len(nexta) != 0:
    nowp = nexta.pop(0)
    if nowp in way:
        for i in way[nowp]:
            cld[i] = nowp
            nexta.append(i)
ans = [0] * (n + 1)
for i in cld:
    ans[i] = cld[i]
for i in range(1, n + 1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b
import sys
sys.setrecursionlimit(1000000)
from collections import deque

n, m = getMN()

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]

k = m-1+n
for i in range(k):
    p1,p2 = getMN()
    parents[p2].append(p1)
    childs[p1].append(p2)

dst = [0 for i in range(n+1)]

d = deque()
n_root = 0
for i, x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

def bfs(n_cur):
    for c in childs[n_cur]:
        d.append(c)
        dst[c] = max(dst[c], dst[n_cur]+1)
    while(d):
        bfs(d.pop())

bfs(n_root)

for plist in parents[1:]:
    if plist:
        cur = -1
        ans = plist[0]
        for p in plist:
            if dst[p] > cur:
                cur = dst[p]
                ans = p
        print(ans)
    else:
        print(0)

Submission status: Time Limit Exceeded

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

def f(n, parent, depth):
    if start[n-1] >= 0:
        if depth > d[n-1]:
            start[n-1] = parent
            d[n-1] = depth
        return
    start[n-1] = parent
    d[n-1] = depth
    for i in range(N+M-1):
        if data[i][0] == n:
            f(data[i][1], data[i][0], depth+1)


for i in range(N):
    start = [-1]*N
    d = [-1]*N
    f(i+1, 0, 0)
    if min(start) == 0:
        for i in start:
            print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())

fromR = {i:[] for i in range(N+1)}
toR = {i:[] for i in range(N+1)}

ans = [-1 for i in range(N+1)]

for _ in range(N-1+M):
    a,b=map(int,input().split())
    fromR[a].append([b,a])
    toR[b].append(a)

r=1
while len(toR[r])>0:
    r=toR[r][0]

ans[r]=0

que = fromR[r]

while len(que)>0:
    tmp=[]
    for q in que:
        b,a=q
        flag=True
        for p in toR[b]:
            flag = flag and ans[p]!=-1
            if flag==False:
                break
        if flag:
            ans[b]=a
            tmp+=fromR[b]
    que=tmp
for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge_from = [set() for _ in range(N+1)]
edge_to = [set() for _ in range(N+1)]
ans = [-1]*(N+1)
child = set()
parent = set()
for _  in range(N-1+M):
    go,to = map(int,input().split())
    edge_from[go].add(to)
    edge_to[to].add(go)
    child.add(to)
for i in range(1,N+1):
    if i not in child:
        parent.add(i)
        par = i
        break
from collections import deque
stack = deque()
stack.append(par)
distance = [-1]*(N+1)
distance[par] = 0
while stack:
    v = stack.popleft()
    for i in edge_from[v]:
        ok = True
        for j in edge_to[i]:
            if j not in parent:
                ok = False
        if ok:
            distance[i] = distance[v] + 1
            stack.append(i)
            parent.add(i)
        else:
            continue
dis = [set() for _ in range(max(distance)+1)]
for i in range(1,N+1):
    dis[distance[i]].add(i)
for i in range(1,N+1):
    if i == par :
        ans[i] = 0
    else:
        for j in dis[distance[i]-1]:
            if j in edge_to[i]:
                ans[i] = j
                break
for i in range(1,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
s=input().split()
n,m=int(s[0]),int(s[1])
a=[]
b=[]
isroot=[]
depth=[]
level=[]
decendent=[]
parent=[]
for i in range(n+1):
    isroot.append(1)
    depth.append(-1)
    decendent.append([])
    parent.append([])
    level.append([])
isroot[0]=0
#depth[0]=0
root=0
for i in range(n+m-1):
    s=input().split()
    A,B=int(s[0]),int(s[1])
    a.append(A)
    b.append(B)
    decendent[A].append(B)
    parent[B].append(A)
    isroot[B]=0
for i in range(1,n+1):
    if isroot[i]:
        root=i
        break
depth[root]=0
level[0].append(root)
t=True
for k in range(n+2):
    if t:
        t=False
        for i in level[k]:
                t=True
                for j in decendent[i]:
                    depth[j]=k+1
                    level[k+1].append(j)
                    if level[k].count(j):
                        level[k].remove(j)
for i in range(1,n+1):
    if root==i:
        print(0)
    else:
        for j in parent[i]:
            if depth[j]==depth[i]-1:
                print(j)
                break

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
ans = [[-1,-1] for i in range(n)]
ans[ne] = [0,0]
def dfs(x,y,z):
        for i in g[x]:
                if i == y:
                        continue
                if ans[i][1] < z+1:
                        ans[i] = [x+1,z+1]
                        heapq.heappush(que,[z+1,i,x])
que = [[0,ne,-1]]
heapq.heapify(que)
while que:
        c,a,b = heapq.heappop(que)
        dfs(a,b,c)
for i,j in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
n,m = map(int,input().split())
g2 = [[] for i in range(n)]
g = [[] for i in range(n)]
for i in range(n-1+m):
        a,b = map(int,input().split())
        g2[b-1].append(a-1)
        g[a-1].append(b-1)
for j in range(n):
        if len(g2[j]) == 0:
                ne = j
                break
ans = [[-1,-1] for i in range(n)]
ans[ne] = [0,0]
def dfs(x,y,z):
        for i in g[x]:
                if i == y:
                        continue
                if ans[i][1] < z+1:
                        ans[i] = [x+1,z+1]
                        dfs(i,x,z+1)
dfs(ne,-1,0)
for i,j in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = {i:[] for i in range(N)}
X = [0]*(N)
searched = [0]*(N)
pairents = [-1]*N

for _ in range(N-1+M):
    a, b = inpl()
    G[a-1].append(b-1)
    X[b-1] += 1

q = X.index(0)

Q = deque([q])
while Q:
    p = Q.popleft()
    for q in G[p]:
        if searched[q] <= searched[p]:
            searched[q] = searched[p] + 1
            Q.append(q)

for a in range(N):
    for b in G[a]:
        if searched[b] == searched[a] + 1:
            pairents[b] = a
for p in pairents:
    print(p+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq as hq
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ans
    for t in rg[s]:
        return dfs(t)
    else:
        ans[s] = 0
        return s


def bfs(s, dep):
    global ans
    global dist
    h = [[-dep, s]]
    while h:
        d, u = hq.heappop(h)
        if dist[u] > -d:
            continue
        for v in g[u]:
            if dist[v] <= dist[u] + 1:
                ans[v] = u + 1
                dist[v] = dist[u] + 1
                hq.heappush(h, [-(-d + 1), v])


ans = [None] * N
dist = [0] * N
s = dfs(0)
bfs(s, 0)

for x in ans:
    print(x)