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:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""

#B
"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""

#C
"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""

#D
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
for a,b in c:
    v[a].append(b)
    ins[b] += 1
ans = [-1 for i in range(n)]
q = []
for i in range(n):
    if ins[i] == 0:
        q.append(i)
i = -1
lis = [True for i in range(n)]
while q:
    i = q.pop(0)
    for j in v[i]:
        ans[j] = i
        ins[j] -= 1
        if ins[j] == 0:
            q.append(j)
for i in ans:
    print(i+1)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m = [int(i) for i in input().split()]
a = [0]*(n+m+1)
b = [0]*(n+m+1)
parents = [-1]*n
child = [[] for _ in range(n)]
for i in range(n+m-1):
    a[i], b[i] = [int(i) - 1 for i in input().split()]
    parents[b[i]] = a[i]
    child[a[i]].append(b[i])
root = 0
for i in range(n):
    if parents[i] == -1:
        root = i
        break
_queue = queue.Queue()
for i in child[root]:
    _queue.put([root, i])
parents = [-1 for _ in range(n)]
for k in range(10**10):
    size = _queue.qsize()
    if size == 0:
        break
    for i in range(size):
        _par, _child = _queue.get()
        # print("child:{} par:{}".format(_child, _par))
        parents[_child] = _par
        for j in child[_child]:
            _queue.put([_child, j])
for _par in parents:
    print(_par+1)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

import sys
sys.setrecursionlimit(200000)


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

A, B = [], []
to = [[] for i in range(N)]

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


class Node:
    def __init__(self):
        self.parent = set()
        self.children = set()
        self.deep = 0
        self.res = 0


nodes = [Node() for _ in range(N + 1)]

for a, b in zip(A, B):
    nodes[b].parent.add(a)
    nodes[a].children.add(b)

root_num = int(list(set(A) - set(B))[0])


def traverse(root):
    # for p in root.parent:
    #     root.anc = root.anc.union(nodes[p].anc)
    #     root.anc = root.anc.union(nodes[p].parent)
    for c in root.children:
        if nodes[c].deep < root.deep + 1:
            nodes[c].deep = max(nodes[c].deep, root.deep + 1)
            traverse(nodes[c])


traverse(nodes[root_num])

for i in range(1, N + 1):
    deep = nodes[i].deep
    if deep == 0:
        nodes[i].res = 0
    for p in nodes[i].parent:
        if nodes[p].deep == deep - 1:
            nodes[i].res = p
            break

for i in range(1, N + 1):
    print(nodes[i].res)


# for i in range(1, N + 1):
#     rm = []
#     for p in nodes[i].parent:
#         if p in nodes[i].anc:
#             rm.append(p)
#     for p in rm:
#         nodes[i].parent.remove(p)
#         nodes[p].children.remove(i)

# for i in range(1, N + 1):
#     if len(nodes[i].parent) == 0:
#         print(0)
#     else:
#         print(list(nodes[i].parent)[0])

Submission status: Time Limit Exceeded

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


def BellmanFord(edges, num_v, source):
    #グラフの初期化
    inf = float("inf")
    dist = np.zeros(num_v)
    dist[:] = np.inf
    dist[source] = 0
    parent = np.zeros(num_v, dtype=int)

    #辺の緩和
    for i in range(num_v):
        for fr, to, w in edges:
            if dist[to] > dist[fr] + w:
                dist[to] = dist[fr] + w
                parent[to] = fr
                if i == num_v-1:
                    return -1, None
    return dist, parent

def solve():
    N, M = map(int, input().split())
    TO = np.zeros(N)
    edges = []
    for _ in range(N+M-1):
        f, t = map(int, input().split())
        f -= 1
        t -= 1
        TO[t] += 1
        edges.append((f, t, -1))
    start = TO.argmin()
    _, parent = BellmanFord(edges, N, start)
    
    for i in range(N):
        if i==start:
            print(0)
        else:
            print(parent[i]+1)



if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import queue

N, M = (int(i) for i in input().split())
G = [[] for i in range(N)]
R = [[] for i in range(N)]
for i in range(N+M-1):
    A, B = (int(i) for i in input().split())
    G[A-1].append(B-1)
    R[B-1].append(A-1)

for i in range(N):
    if len(R[i]) == 0:
        oya = i
        break

prev = [-1] * N
v = queue.Queue()
v.put(oya)
while not v.empty():
    now = v.get()
    if G[now]:
        for u in G[now]:
            prev[u] = now
            v.put(u)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Edge2 = defaultdict(lambda: [])

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

Submission status: Time Limit Exceeded

Solution code:
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 heapq import *

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

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

for i in range(1, N + 1):
    if not ws[i]:
        root = i
        break

h = []

heappush(h, (0, root, 0))

rs = [-1] * (N + 1) 
ls = [0] * (N + 1)

rs[root] = 0

#print(vs)

while h:
    l, n, parent = heappop(h)
    #print("*", l, n, parent)
    for m in vs[n]:
        if ls[m] > l - 1:
            #print("+", l -1, m, n)
            ls[m] = l - 1
            prer = rs[m]
            if prer != n and prer in vs[m]:
                vs[m].remove(prer)
            rs[m] = n
            heappush(h, (l - 1, m, n))

for i in range(1, N + 1):
    print(rs[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)
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:
N,M = map(int,input().split())
A = [[0 for i in range(N + 2)] for j in range(N + 2)]
B = [[0 for i in range(N + 2)] for j in range(N + 2)]
for i in range(N - 1 + M):
  a,b = map(int,input().split())
  A[a][A[a][0] + 1] = b
  A[a][0] += 1
  B[b][B[b][0] + 1] = a
  B[b][0] += 1
node = 0
for i in range(1,N):
  if B[i][0] == 0:
    node = i
    break

ans = [0] * (N + 1)
q = []
nq = []
q.append(node)
while len(q) > 0:
  for n in q:
    for i in range(1,A[n][0] + 1):
      if ans[A[n][i]] != 0 and B[A[n][i]][0] <= 1:
        continue
      nq.append(A[n][i])
      ans[A[n][i]] = n
  q = nq
  nq = []

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

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:
            ans[b]=a
            tmp+=fromR[b]
    que=tmp
for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m = [int(i) for i in input().split()]
a = [0]*(n+m+1)
b = [0]*(n+m+1)
parents = [-1]*n
child = [[] for _ in range(n)]
for i in range(n+m-1):
    a[i], b[i] = [int(i) - 1 for i in input().split()]
    parents[b[i]] = a[i]
    child[a[i]].append(b[i])
root = 0
for i in range(n):
    if parents[i] == -1:
        root = i
        break
_queue = queue.Queue()
for i in child[root]:
    _queue.put([root, i])
parents = [-1 for _ in range(n)]
while 1:
    size = _queue.qsize()
    if size == 0:
        break
    for i in range(size):
        _par, _child = _queue.get()
        # print("child:{} par:{}".format(_child, _par))
        parents[_child] = _par
        for j in child[_child]:
            _queue.put([_child, j])
for _par in parents:
    print(_par+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
adjL = [[] for v in range(N)]
indegs = [0] * N
for _ in range(N+M-1):
    u, v = map(int, input().split())
    adjL[u-1].append(v-1)
    indegs[v-1] += 1

parents = [-1] * N
vRoot = [v for v in range(N) if indegs[v] == 0][0]
vNows = set([vRoot])
for _ in range(N+M):
    vNexts = set()
    for vNow in vNows:
        for v2 in adjL[vNow]:
            parents[v2] = vNow
            vNexts.add(v2)
    vNows = vNexts

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

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
arr = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
checked = []
queue = []
parent_count = [0 for _ in range(N)]
for _ in range(N+M-1):
    A, B = list(map(int, input().split()))
    if not B-1 in arr[A-1]:
        arr[A-1].append(B-1)
        parent_count[B-1] += 1
    
for i in range(N):
    if parent_count[i] == 0:
        queue.append(i)

while 1:
    if len(queue) == 0:
        break
    from_ = queue.pop(0)
    x = arr[from_]
    for to_ in x:
        if parent_count[to_] > 1:
            parent_count[to_] -= 1
            continue
        ans[to_] = from_+1
        queue.append(to_)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if len(Edge[en]) == 1:
                Q.append(en)
            else:
                Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
number = [[-1, -1] for i in range(n)]
tree = [[] for i in range(n)]
for i in range(n - 1 + m):
    a, b = map(int, input().split())
    tree[b - 1].append(a)
nagasa = []
for i in range(n):
    nagasa.append((i, len(tree[i])))
nagasa = sorted(nagasa, key=itemgetter(1))
nokori = set()
while True:
    for j in range(n):
        i = nagasa[j][0]
        if number[i][0] != -1:
            continue
        if len(tree[i]) == 1:
            if number[tree[i][0] - 1][1] == -1:
                nokori.add(i)
                continue
            number[i] = [tree[i][0], number[tree[i][0] - 1][1] + 1]
        elif len(tree[i]) == 0:
            number[i] = [0, 0]
        else:
            kari = []
            m = 0
            flag = 0
            for k in tree[i]:
                if number[k - 1][1] == -1:
                    nokori.add(i)
                    flag = 1
                    break
                kari.append((k, number[k - 1][1] + 1))
                m = max(m, number[k - 1][1] + 1)
            if flag:
                continue
            for k in kari:
                if k[1] == m:
                    number[i] = k
                    break
        nokori.discard(i)
    if len(nokori) == 0:
        break
for i in number:
    print(i[0])

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.pop()
    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:
# import numpy as np

import sys
sys.setrecursionlimit(200000)


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

A, B = [], []
to = [[] for i in range(N)]

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


class Node:
    def __init__(self):
        self.parent = set()
        self.children = set()
        self.deep = 0
        self.res = 0


nodes = [Node() for _ in range(N + 1)]

for a, b in zip(A, B):
    nodes[b].parent.add(a)
    nodes[a].children.add(b)

root_num = int(list(set(A) - set(B))[0])


def traverse(root):
    # for p in root.parent:
    #     root.anc = root.anc.union(nodes[p].anc)
    #     root.anc = root.anc.union(nodes[p].parent)
    for c in root.children:
        nodes[c].deep = max(nodes[c].deep, root.deep + 1)
        traverse(nodes[c])


traverse(nodes[root_num])

for i in range(1, N + 1):
    deep = nodes[i].deep
    if deep == 0:
        nodes[i].res = 0
    for p in nodes[i].parent:
        if nodes[p].deep == deep - 1:
            nodes[i].res = p
            break

for i in range(1, N + 1):
    print(nodes[i].res)


# for i in range(1, N + 1):
#     rm = []
#     for p in nodes[i].parent:
#         if p in nodes[i].anc:
#             rm.append(p)
#     for p in rm:
#         nodes[i].parent.remove(p)
#         nodes[p].children.remove(i)

# for i in range(1, N + 1):
#     if len(nodes[i].parent) == 0:
#         print(0)
#     else:
#         print(list(nodes[i].parent)[0])

Submission status: Time Limit Exceeded

Solution code:
s=input().split()
n,m=int(s[0]),int(s[1])
a=[]
b=[]
isroot=[]
depth=[]
decendent=[]
parent=[]
for i in range(n+1):
    isroot.append(1)
    depth.append(-1)
    decendent.append([])
    parent.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
t=True
for k in range(n+2):
    if t:
        t=False
        for i in range(1,n+1):
            if depth[i]==k:
                t=True
                for j in decendent[i]:
                    depth[j]=k+1
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:
#!/usr/bin/env python
import numpy as np
from collections import deque


def BellmanFord(edges, num_v, source):
    #グラフの初期化
    inf = float("inf")
    dist = [inf for i in range(num_v)]
    dist[source] = 0
    parent = np.zeros(num_v, dtype=int)

    #辺の緩和
    for i in range(num_v):
        for fr, to, w in edges:
            if dist[to] > dist[fr] + w:
                dist[to] = dist[fr] + w
                parent[to] = fr
                if i == num_v-1:
                    return -1, None
    return dist, parent

def solve():
    N, M = map(int, input().split())
    TO = np.zeros(N)
    # G = [[] for _ in range(N)]
    edges = []
    for _ in range(N+M-1):
        f, t = map(int, input().split())
        f -= 1
        t -= 1
        TO[t] += 1
        # G[f].append([t, -1])
        edges.append((f, t, -1))
    start = TO.argmin()
    _, parent = BellmanFord(edges, N, start)
    
    for i in range(N):
        if i==start:
            print(0)
        else:
            print(parent[i]+1)



if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
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()
    if v != par:
        for i in edge_to[v]:
            if i not in parent: continue
    for u in edge_from[v]:
        distance[u] = max(distance[v] + 1,distance[u])
        stack.append(u)
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:
N, M = list(map(int, input().split()))
arr = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
checked = []
queue = []
parent_count = [0 for _ in range(N)]
for _ in range(N+M-1):
    A, B = list(map(int, input().split()))
    arr[A-1].append(B-1)
    
    
    
for i in range(N):
    arr[i] = list(set(arr[i]))
    
for i in range(N):
    for j in range(N):
        if i in arr[j]:
            parent_count[i] += 1
    if parent_count[i] == 0:
        queue.append(i)

while 1:
    if len(queue) == 0:
        break
    from_ = queue.pop(0)
    x = arr[from_]
    for to_ in x:
        if parent_count[to_] > 1:
            parent_count[to_] -= 1
            continue
        ans[to_] = from_+1
        queue.append(to_)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N,M =[int(i)for i in input().split()]
ko =[[] for i in range(N)]
tyo =set([i for i in range(N)])
for _ in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    tyo = tyo - {B-1}
    ko[A-1].append(B-1)
tyo =list(tyo)
tyouten =tyo[0]
rank =[[-1,-1]for _ in range(N)]
def keisan(num,no,bef):
    if rank[num][0] < no:
        rank[num]=[no,bef+1]
    else:
        return
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
ans =""
for i in rank:
    ans =ans +str(i[1])+"\n"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
n,a,b = LI()
ans = [min(a,b),max(0,a+b-n)]
print(ans[0],ans[1])
"""

#B
"""
n = II()
a = S()
b = S()
c = S()
ans = 0
for i in range(n):
    if a[i] == b[i]:
        if b[i] == c[i]:
            continue
        else:
            ans += 1
    else:
        if b[i] == c[i] or c[i] == a[i]:
            ans += 1
        else:
            ans += 2
print(ans)
"""

#C
"""
n = II()
c = LIR(n)
c.sort(key = lambda x:-x[0]-x[1])
ans = 0
i = 0
for i in range(n):
    x,y = c.pop(0)
    if i%2 == 0:
        ans += x
    else:
        ans -= y
print(ans)
"""

#D
n,m = LI()
c = LIR(n-1+m)
for i in range(n-1+m):
    c[i][0] -= 1
    c[i][1] -= 1
l = []
v = [[] for i in range(n)]
ins = [0 for i in range(n)]
d = [[] for i in range(n)]
for a,b in c:
    v[a].append(b)
    ins[b] += 1
ans = [-1 for i in range(n)]
q = []
for i in range(n):
    if ins[i] == 0:
        q.append(i)
i = -1
lis = [True for i in range(n)]
while q:
    i = q.pop(0)
    for j in v[i]:
        ans[j] = i
        ins[j] -= 1
        if ins[j] == 0:
            q.append(j)
for i in ans:
    print(i+1)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split())
ko=[[] for i in range(n)]
oya=[[] for i in range(n)]
rank=[0]*n 
for i in range(n-1+m):
    a,b=map(int, input().split())
    ko[b-1].append(a-1)
    oya[a-1].append(b-1)
from collections import deque
s=0
for i in range(n):
    if not ko[i]:s=i
p=deque([s])
p2={s}
nr=1
ans=[0]*n
while p:
    now=p.popleft()
    p2.remove(now)
    nr=rank[now]+1
    for i in oya[now]:
        rank[i]=nr
        ans[i]=now+1
        if i not in p2:
            p.append(i)
            p2.add(i)
for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
reverse_path_dict = {}
for i in range(n):
  reverse_path_dict[i+1] = []
for i in range(n+m-1):
  f, t = map(int, input().split())
  reverse_path_dict[t].append(f)

def rec_get_max_path(path_list=[]):
  current_node = path_list[-1]
  path_cand = reverse_path_dict[current_node]
  if len(path_cand) == 0:
    return path_list
  res_path_list = []
  for c in path_cand:
    tmp_path_list = copy.deepcopy(path_list)
    tmp_path_list.append(c)
    tmp_res_path_list = rec_get_max_path(tmp_path_list)
    if len(tmp_res_path_list) > len(res_path_list):
      res_path_list = tmp_res_path_list
  for j in range(len(res_path_list)-1):
      reverse_path_dict[res_path_list[j]] = [res_path_list[j+1]]
  return res_path_list

for i in range(n):
  path_cand = reverse_path_dict[i+1]
  if len(path_cand) == 0:
    print(0)
  elif len(path_cand) == 1:
    print(path_cand[0])
  else:
    res_path_list = rec_get_max_path([i+1])
    print(res_path_list[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:
INF = 10**100
N,M = map(int,input().split())
parent = [-1 for i in range(N)]
edge_raw = []
edge = [[] for i in range(N)]
dist = [INF for i in range(N)]
edge_inv = [[] for i in range(N)]
remain = [i for i in range(N)]
for i in range(N+M-1):
	a,b = map(int,input().split())
	s,t = a-1, b-1
	edge[s].append(t)
	edge_inv[t].append(s)
	edge_raw.append((s,t))

root = [i for i in range(N) if len(edge_inv[i]) == 0][0]
dist[root] = 0
updated = True
while updated:
	updated = False
	for s,d in edge_raw:
		if dist[s] != INF:
			if dist[d] > dist[s] - 1:
				parent[d] = s
				dist[d] = dist[s] - 1
				updated = True
for i in range(N):
	print(parent[i] + 1)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


def get_root(A):
    res = [A]
    search = [A]
    visit = [False for i in range(N)]
    while(len(search) > 0):
        now = search.pop()
        if visit[now-1]:
            continue
        visit[now-1] = True
        for a in ans[now-1]:
            if a == 0:
                continue
            if visit[a-1]:
                continue
            res.append(a)
            search.append(a)
    return set(res)


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

AB = sorted(AB, key=itemgetter(1))
count = 1
before = -1
temp = [AB[0][0]]
ans = [[0, ] for i in range(N)]
before = AB[0][1]

for a, b in AB[1:]:
    if before != b:
        ans[before-1] = temp
        temp = [a, ]
        before = b
    else:
        temp.append(a)

if len(temp) > 0:
    ans[-1] = (temp)

new_ans = []
for each_ans in ans:
    if len(each_ans) == 1:
        new_ans.append(each_ans[0])
        continue
    for a in each_ans:
        setans = set(each_ans)
        if len(setans & get_root(a)) == len(setans):
            new_ans.append(a)
            break

for line in new_ans:
    print(line)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)

Submission status: Time Limit Exceeded

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

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

to_par = {i: [] for i in range(1, N+1)}
to_chi = {i: [] for i in range(1, N+1)}
con_list = []
for _ in range(N - 1 + M):
    a, b = ds_in()
    to_par[b].append(a)
    to_chi[a].append(b)

for i in range(1, N+1):
    if len(to_par[i]) == 0:
        node = i


TREE = {i: (-1, -1) for i in range(1, N+1)}


def depth_search(par, cand, depth):
    if TREE[cand][1] < depth:
        TREE[cand] = (par, depth)
    for child in to_chi[cand]:
        depth_search(cand, child, depth + 1)


depth_search(0, node, 0)

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

Submission status: Time Limit Exceeded

Solution code:
s=input().split()
n,m=int(s[0]),int(s[1])
a=[]
b=[]
isroot=[]
depth=[]
decendent=[]
parent=[]
for i in range(n+1):
    isroot.append(1)
    depth.append(-1)
    decendent.append([])
    parent.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
for k in range(n+2):
    for i in range(1,n+1):
        if depth[i]==k:
            for j in decendent[i]:
                depth[j]=k+1
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 queue

N,M = map(int,input().split())
A = [[0 for i in range(N + 2)] for j in range(N + 2)]
B = [[0 for i in range(N + 2)] for j in range(N + 2)]
for i in range(N - 1 + M):
  a,b = map(int,input().split())
  A[a][A[a][0] + 1] = b
  A[a][0] += 1
  B[b][B[b][0] + 1] = a
  B[b][0] += 1
node = 0
for i in range(1,N):
  if B[i][0] == 0:
    node = i
    break

ans = [0] * (N + 1)
q = queue.Queue()
q.put(node)
while not q.empty():
  n = q.get()
  for i in range(1,A[n][0] + 1):
    if ans[A[n][i]] != 0 and B[A[n][i]][0] <= 1:
      continue
    q.put(A[n][i])
    ans[A[n][i]] = n

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