Problem:


Score : 500 points

Problem Statement

There is a rooted tree (see Notes) with N vertices numbered 1 to N.
Each of the vertices, except the root, has a directed edge coming from its parent.
Note that the root may not be Vertex 1.

Takahashi has added M new directed edges to this graph.
Each of these M edges, u \rightarrow v, extends from some vertex u to its descendant v.

You are given the directed graph with N vertices and N-1+M edges after Takahashi added edges.
More specifically, you are given N-1+M pairs of integers, (A_1, B_1), ..., (A_{N-1+M}, B_{N-1+M}), which represent that the i-th edge extends from Vertex A_i to Vertex B_i.

Restore the original rooted tree.

Notes

For "tree" and other related terms in graph theory, see the article in Wikipedia, for example.

Constraints

3 \leq N

1 \leq M

N + M \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

If i \neq j, (A_i, B_i) \neq (A_j, B_j).

The graph in input can be obtained by adding M edges satisfying the condition in the problem statement to a rooted tree with N vertices.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_{N-1+M} B_{N-1+M}

Output

Print N lines.
In the i-th line, print 0 if Vertex i is the root of the original tree, and otherwise print the integer representing the parent of Vertex i in the original tree.

Note that it can be shown that the original tree is uniquely determined.

Sample Input 1

3 1
1 2
1 3
2 3

Sample Output 1

0
1
2

The graph in this input is shown below:

It can be seen that this graph is obtained by adding the edge 1 \rightarrow 3 to the rooted tree 1 \rightarrow 2 \rightarrow 3.

Sample Input 2

6 3
2 1
2 3
4 1
4 2
6 1
2 6
4 6
6 5

Sample Output 2

6
4
2
0
6
2



Sample input:
3 1
1 2
1 3
2 3


Sample output:
0
1
2

Submission status: Time Limit Exceeded

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

# Set max recursion limit
sys.setrecursionlimit(1000000)


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


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


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


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


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

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

    return v


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


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

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

    return v


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

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

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

        cps = n_cps[:]

    return dfk


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

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

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

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

    return


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


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

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

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

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

    return result

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

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

dp = None

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

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

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

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

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

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

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

    # print("root", root)

    A = [0] * N

    Layer = [[root]]

    parent_nodes = [root]

    i = 1
    while len(Layer[i-1]) != 0:
        Layer.append([])
        new_parent_nodes = []
        for parent_node in parent_nodes:
            Layer[i].extend(Link[parent_node])
            Layer[i] = list(set(Layer[i]))
                
        
        parent_nodes = Layer[i]
        i += 1

    Layer = Layer[:-1]

    for i in range(len(Layer)):
        Layer[i] = list(set(Layer[i]))
    # print("Layer", Layer)

    X = [[False] * (N+1) for _ in range(len(Layer))]

    for i, L in enumerate(Layer):
        for l in L:
            X[i][l] = True

    i = len(Layer) - 1
    while i >= 0:
        # print(Layer)
        L = Layer[i]
        for l in L:

            maybe_parents = iLink[l]

            for maybe_parent in maybe_parents:
                if X[i-1][maybe_parent]:
                    A[l-1] = maybe_parent

                    j = i - 1
                    while j >= 0:
                        Layer[j] = list(filter(lambda a:a != l, Layer[j]))
                        j -= 1

                    break

        i -= 1
    
    for a in A:
        print(a)


                


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(200000)


def nextis(now_node_i, hierarchy):
    for next_node_i in nodes[now_node_i]["children"]:
        if touched[next_node_i]["touched"] is False:
            touched[next_node_i]["touched"]=True
            touched[next_node_i]["parent"] = now_node_i
            touched[next_node_i]["hierarchy"] = hierarchy
            nextis(next_node_i, hierarchy+1)
        else:
            if hierarchy > touched[next_node_i]["hierarchy"]:
                touched[next_node_i]["parent"] = now_node_i
                touched[next_node_i]["hierarchy"] = hierarchy
                nextis(next_node_i, hierarchy+1)
        

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

nodes = [{"parents":[],"children":[]} for _ in range(n)]
for edge in range(n+m-1):
    a,b = map(int,input().split())
    nodes[a-1]["children"].append(b-1)
    nodes[b-1]["parents"].append(a-1)

# 親を探す
root=None
for i, node in enumerate(nodes):
    if node["parents"]==[]:
        root=i
touched = [{"touched":False,"parent":None,"hierarchy":None} for _ in range(n)]
touched[root]["touched"]=True
nextis(root,0)
for i in range(n):
    if touched[i]["parent"] is None:
        print(0)
    else:
        print(touched[i]["parent"]+1)

Submission status: Time Limit Exceeded

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

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

D = [0] * (n+1)
P = [0] * (n+1)

def dfs(p, i, depth):
    if depth > D[i]:
        D[i] = depth
        P[i] = p
        for t in T[i]:
            dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)

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

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

h = []
heappush(h, (0, 1))
cs = {1: 1}
while h:
    l, n = heappop(h)
    if ws[n]:
        for m in ws[n]:
            if not m in cs:
                cs[m] = 1
                heappush(h, (l + 1, m))
    else:
        root = n

h = []

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

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

ls = defaultdict(int)
ls[root] = 0

while h:
    l, n, parent = heappop(h)
    rs[n] = parent
    for m in vs[n]:
        if ls[m] < l + 1:
            heappush(h, (l + 1, m, n))
            ls[m] = l + 1

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(200000)


def nextis(now_node_i, hierarchy):
    for next_node_i in nodes[now_node_i]["children"]:
        if touched[next_node_i]["touched"] is False:
            touched[next_node_i]["touched"]=True
            touched[next_node_i]["parent"] = now_node_i
            touched[next_node_i]["hierarchy"] = hierarchy
        else:
            if hierarchy > touched[next_node_i]["hierarchy"]:
                touched[next_node_i]["parent"] = now_node_i
                touched[next_node_i]["hierarchy"] = hierarchy
        nextis(next_node_i,hierarchy+1)
        

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

nodes = [{"parents":[],"children":[]} for _ in range(n)]
for edge in range(n+m-1):
    a,b = map(int,input().split())
    nodes[a-1]["children"].append(b-1)
    nodes[b-1]["parents"].append(a-1)

# 親を探す
root=None
for i, node in enumerate(nodes):
    if node["parents"]==[]:
        root=i
touched = [{"touched":False,"parent":None,"hierarchy":None} for _ in range(n)]
touched[root]["touched"]=True
nextis(root,0)
for i in range(n):
    if touched[i]["parent"] is None:
        print(0)
    else:
        print(touched[i]["parent"]+1)

Submission status: Time Limit Exceeded

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

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [[] for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].append(a)

D = [0] * (n+1)
P = [0] * (n+1)

def dfs(p, i, depth):
    if depth > D[i]:
        D[i] = depth
        P[i] = p
    for t in T[i]:
        dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(RT[i][0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)

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])
nr=1
ans=[0]*n
while p:
    now=p.popleft()
    nr=rank[now]+1
    p.extend(oya[now])
    for i in oya[now]:
        rank[i]=nr
        ans[i]=now+1
for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
def topological_sort(V, to):
    cnt = [0]*V
    s = []
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = []
    for i in range(V):
        if cnt[i] == 0:
            Q.append(i)
    while len(Q) > 0:
        i = Q[0]
        del Q[0]
        s.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return s

N,M = map(int,input().split())
to = [[] for i in range(N)]
From = [[] for i in range(N)]
for i in range(N-1+M):
    x, y = list(map(int,input().split()))
    to[x-1].append(y-1)
    From[y-1].append(x-1)
s = topological_sort(N, to)
s = [(s[i],i) for i in range(N)]
s.sort()
for i in range(N):
    k = -1
    I = -1
    for j in From[i]:
        if k < s[j][1]:
            k = s[j][1]
            I = j
    print(I+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    parents = [[] for _ in range(N+1)]
    childs = [[] for _ in range(N+1)]
    for i in range(N+M-1):
        a, b = map(int, input().split())
        childs[a].append(b)
        parents[b].append(a)
    root = -1
    for i in range(1, N+1):
        if len(parents[i]) == 0:
            root = i
            break
    originalParent = [-1] * (N+1)
    q = deque([])
    q.append((root, 0))
    while(len(q)):
        n, parent = q.popleft()
        originalParent[n] = parent
        for c in childs[n]:
            q.append((c, n))
    for i in range(1, N+1):
        print(originalParent[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

v = [[] for i in range(N + 1)]
vin = [0 for i in range(N + 1)]

parent = [0 for i in range(N + 1)]
# visited = [False for i in range(N + 1)]

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

Q = deque()
for i in range(1, N + 1):
    if vin[i] == 0:
        Q.append((i, 0))
        break

while len(Q) != 0:
    now, pa = Q.popleft()
    parent[now] = pa
    # if visited[now]:
    #     continue
    for i in v[now]:
        Q.append((i, now))
    # visited[now] = True

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


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

distance = {i:0 for i in range(n)}

queue = deque()
queue.append(root)
while queue:
    pos = queue.popleft()
    # print('pos',pos)
    children = child[pos]
    pos_dist = distance[pos]
    for c in children:
        # print('c,parent,dist',c,parent[c],distance[c])
        if distance[c]<pos_dist+1:
            distance[c] = pos_dist+1
            parent[c] = pos
            # print('c,update',c, parent[c],distance[c])
        queue.append(c)
# print(distance)
# print(parent)

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

Submission status: Time Limit Exceeded

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import numpy as np
n,m=IL()
nl=[[] for j in range(n)]
nl2=[[0 for i in range(n)] for j in range(n)]
dub=[0 for i in range(n)]
for i in range(n-1+m):
    a,b=IL()
    nl[a-1].append(b-1)
    nl2[a-1][b-1]=1
    dub[b-1]+=1
def anpath(a,b):
    q=[]
    for i in nl[a]:
        if i!=b:
            q.append(i)
    while len(q)!=0:
        t=q.pop(0)
        if t==b:
            return True
        for i in nl[t]:
            q.append(i)
    return False
for i in range(n):
    if dub[i]==0:
        top=i
    elif dub[i]>=2:
        for j in range(n):
            if nl2[j][i]==1:
                if anpath(j,i):
                    nl2[j][i]=0
                else:
                    nl2[j][i]=2
                    break
nl2=np.array(nl2)
ans=np.argmax(nl2,axis=0)
for i in range(n):
    if i==top:
        print(0)
    else:
        print(ans[i]+1)

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 len(ko[i])==0:s=i
p=deque([s])
nr=1
ans=[0]*n
while p:
    now=p.popleft()
    nr=rank[now]+1
    p.extend(oya[now])
    for i in oya[now]:
        rank[i]=nr
        ans[i]=now+1
for i in ans:print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A = defaultdict(list)
D = defaultdict(list)
DLen = defaultdict(int)
R = [i for i in range(1,N+1)]
for i in range(N+M-1):
    a,b = map(int,input().split())
    A[a].append(b)
    D[b].append(a)
    DLen[b] += 1
    try:
        R.remove(b)
    except ValueError:
        pass
    
D[R[0]].append(0)
Search = [(R[0],A[R[0]])]
Stepd = [R[0]]

while Search:
    now,NEX = Search.pop()
    for s in NEX:
        if DLen[s]>=2:
            DLen[s] -= 1
        else:
            D[s] = [now]
            Stepd.append(s)
            Search.append((s,A[s]))
            
for i in range(1,N+1):
    print(D[i][0])

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

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

h = []
heappush(h, (0, 1))
while h:
    l, n = heappop(h)
    if ws[n]:
        for m in ws[n]:
            heappush(h, (l + 1, m))
    else:
        root = n

h = []

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

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

while h:
    l, n, parent = heappop(h)
    rs[n] = parent
    for m in vs[n]:
        heappush(h, (l + 1, m, n))

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

Submission status: Time Limit Exceeded

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

# Set max recursion limit
sys.setrecursionlimit(1000000)


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


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


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


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


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

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

    return v


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


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

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

    return v


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

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

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

        cps = n_cps[:]

    return dfk


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

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

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

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

    return


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


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

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

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

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

    return result

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

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

dp = None

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

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

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

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

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

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

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

    # print("root", root)

    A = [0] * N

    Layer = [[root]]

    parent_nodes = [root]

    i = 1
    while len(Layer[i-1]) != 0:
        Layer.append([])
        new_parent_nodes = []
        for parent_node in parent_nodes:
            for l in Link[parent_node]:
                Layer[i].append(l)
                
        
        parent_nodes = Layer[i]
        i += 1

    Layer = Layer[:-1]

    for i in range(len(Layer)):
        Layer[i] = list(set(Layer[i]))
    # print("Layer", Layer)

    X = [[False] * (N+1) for _ in range(len(Layer))]

    for i, L in enumerate(Layer):
        for l in L:
            X[i][l] = True

    i = len(Layer) - 1
    while i >= 0:
        # print(Layer)
        L = Layer[i]
        for l in L:

            maybe_parents = iLink[l]

            for maybe_parent in maybe_parents:
                if X[i-1][maybe_parent]:
                    A[l-1] = maybe_parent

                    j = i - 1
                    while j >= 0:
                        Layer[j] = list(filter(lambda a:a != l, Layer[j]))
                        j -= 1

                    break

        i -= 1
    
    for a in A:
        print(a)


                


main()

Submission status: Time Limit Exceeded

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

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


N, M = ds_in()

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)


def find_all_parents(child, par_dict):
    """
    child : int
    """
    all_parents = []
    for p in to_par[child]:
        all_parents.append(p)
        if p in par_dict.keys():
            all_parents.extend(par_dict[p])
        else:
            all_parents.extend(find_all_parents(p, par_dict))
    all_parents = list(set(all_parents))
    return all_parents


parents_dict = {}
for i in range(1, N+1):
    parents_dict[i] = find_all_parents(i, parents_dict)
# parents_dict = {i: find_all_parents(i) for i in range(1, N+1)}

ans = {i: 0 for i in range(1, N+1)}
for child in range(1, N+1):
    par_cand = to_par[child]
    all_par = []
    for p in par_cand:
        all_par.extend(parents_dict[p])
    all_par = list(set(all_par))
    for p in par_cand:
        if p not in all_par:
            ans[child] = p
            break

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


# IPython.embed()

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
arr = [[0 for _ in range(N)] for _ in range(N)]
ans = [0 for _ in range(N)]
checked = []
queue = [0]
for _ in range(N+M-1):
    A, B = list(map(int, input().split()))
    arr[A-1][B-1] = 1
    
for i in range(N):
    count = 0
    for j in range(N):
        count += arr[j][i]
    if count == 0:
        queue = [i]
    
while 1:
    if len(queue) == 0:
        break
    from_ = queue.pop(0)
    x = arr[from_][:]
    for to_, y in enumerate(x):
        if y != 1:
            continue
        count = 0
        for i in range(N):
            count += arr[i][to_]
        if count > 1:
            arr[from_][to_] = 0
            continue
        ans[to_] = from_+1
        queue.append(to_)
for a in ans:
    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 = -1
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 = i
from collections import deque
stack = deque()
stack.append(parent)
distance = [-1]*(N+1)
distance[parent] = 0
while stack:
    v = stack.popleft()
    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 == parent :
        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:
from collections import defaultdict, deque

v, n = map(int, input().split())
n += v -1
es = [[int(x) for x in input().split()] for _ in range(n)]
f = [[]for _ in range(v+1)]
for a, b in es:
    f[b] += [a]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

for i in range(1, v+1):
    j = res.index(i) - 1
    if res[j] and not res[j] in f[i]:j -= 1
    print(res[j])

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)
s=0
for i in range(n):
    if len(ko[i])==0:s=i
p=[s]
nr=1
ans=[0]*n
while p:
    now=p.pop(0)
    nr=rank[now]+1
    p+=oya[now]
    for i in oya[now]:
        rank[i]=nr
        ans[i]=now+1
for i in ans:print(i)

Submission status: Time Limit Exceeded

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

# Set max recursion limit
sys.setrecursionlimit(1000000)


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


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


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


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


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

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

    return v


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


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

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

    return v


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

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

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

        cps = n_cps[:]

    return dfk


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

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

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

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

    return


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


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

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

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

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

    return result

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

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

dp = None

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

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

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

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

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

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

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

    # print("root", root)

    A = [0] * N

    Layer = [[root]]

    parent_nodes = [root]

    i = 1
    while len(Layer[i-1]) != 0:
        Layer.append([])
        new_parent_nodes = []
        for parent_node in parent_nodes:
            for l in Link[parent_node]:
                Layer[i].append(l)
                
        
        parent_nodes = Layer[i]
        i += 1

    Layer = Layer[:-1]

    for i in range(len(Layer)):
        Layer[i] = list(set(Layer[i]))
    # print("Layer", Layer)

    X = [[False] * (N+1) for _ in range(len(Layer))]

    for i, L in enumerate(Layer):
        for l in L:
            X[i][l] = True  

    Kakutei = collections.defaultdict(lambda: False)

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

            maybe_parents = iLink[l]

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


                


main()