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:
N, M = map(int, input().split())

# 辺を保持しつつ根を見つける
edge = [set() for _ in range(N+1)]
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
root = parent.index(0)

# 根から幅優先でたどっていく
ans = [-1] * (N+1)
rank = [0] * (N+1)
q = set([root])
r = 0
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      nq.add(c)
      # 後に来る＝より深い ので上書きしてよいはず
      ans[c] = p
  q = nq

for i in range(1, N+1):
  print(ans[i] if ans[i] > 0 else 0)

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
  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])
    for j in range(len(res_path_list)-1):
      reverse_path_dict[res_path_list[j]] = [res_path_list[j+1]]

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)
            heappush(h, (l - 1, m, n))
            ls[m] = l - 1
            rs[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:
            Layer[i].extend(Link[parent_node])
                
        parent_nodes = Layer[i]
        i += 1

    Layer = Layer[:-1]
    Layer = [list(set(L)) for L in Layer]
    # 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
    Kakutei = collections.defaultdict(lambda: False)
    while i >= 0:
        L = Layer[i]
        sL = set(Layer[i-1])
        for l in L:
            if Kakutei[l]:
                continue

            maybe_parents = iLink[l]
            intersect = set(maybe_parents) & sL

            for inter in intersect:
                A[l-1] = inter
                Kakutei[l] = True

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

main()

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)}
root = [i for i in range(n)]
for _ in range(n-1+m):
    a,b = map(int, input().split())
    child[a-1].append(b-1)
    if b-1 in root:
        root.remove(b-1)

root = root[0]

queue = deque()
queue.append(root)

true_parent = {}
while queue:
    pos = queue.popleft()
    children = child[pos]
    for c in children:
        true_parent[c] = pos    
        if child[c] and len(parent[c])!=1:
            queue.append(c)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    sys.setrecursionlimit(1000000) # recursion limit hack
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    node = []
    unpointed = set()
    for i in range(N):
        node.append(set())
        unpointed.add(i)
    for i in range(N-1+M):
        buf = input()
        buflist = buf.split()
        node[int(buflist[0])-1].add(int(buflist[1])-1)
    for i in range(N):
        for j in node[i]:
            unpointed.discard(j)
    root = unpointed.pop()
    recursion_graph(node, set(), root, root)
    ancestor = []
    for i in range(N):
        ancestor.append(None)
    recursion_ancestor(node, ancestor, root, root)
    for i in range(N):
        if ancestor[i] != None:
            print(ancestor[i]+1)
        else:
            print(0)

def recursion_graph(node, sub, current, last):
    sub = set(sub)
    for e in sub:
        if e[0] != last and e[1] == current:
            node[e[0]].discard(e[1])
    for dest in list(node[current]):
        sub.add((current, dest))
    for dest in list(node[current]):
        recursion_graph(node, sub, dest, current)

def recursion_ancestor(node, ancestor, current, last):
    if current != last:
        ancestor[current] = last
    for dest in list(node[current]):
        recursion_ancestor(node, ancestor, dest, current)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m = [int(i) for i in input().split()]
a = [0 for _ in range(n+m+1)]
b = [0 for _ in range(n+m+1)]
parents = [-1 for _ in range(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
# print("par:{}".format(parents))
# print("child:{}".format(child))
_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:
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 i, each_ans in enumerate(ans):
    if len(each_ans) == 1:
        new_ans.append(each_ans[0])
        continue
    for a in each_ans:
        if set(each_ans) & get_root(a) == set(each_ans):
            new_ans.append(a)
            break

for line in new_ans:
    print(line)

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])
                
        parent_nodes = Layer[i]
        i += 1

    Layer = Layer[:-1]
    Layer = [list(set(L)) for L in Layer]
    # 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 = 1
    while i < len(Layer):
        L = Layer[i]
        sL = set(Layer[i-1])
        for l in L:
            maybe_parents = iLink[l]
            intersect = set(maybe_parents) & sL

            for inter in intersect:
                A[l-1] = inter

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


                


main()

Submission status: Time Limit Exceeded

Solution code:
def anscestor(s, parent):
    ret = []
    if len(parent) == 0:
        return []
    else:
        r = parent[s]
        for el in r:
            ret.append(el)
            ret.append(anscestor(el, parent))
    return ret


def check(l, parent):
    le = len(l)
    for i in range(le):
        a = l[i]
        b = []
        for j in range(le):
            if not i == j:
                b.append(l[j])

        ans = anscestor(a, parent)
        if all(k in ans for k in b):
            return [a]


N, M = map(int, input().split())
nodes = [0]*N

edges = []
mat = [[0]*N for _ in range(N)]

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


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

# 確定している親をparentに代入
for s, g in edges:
    parent[g].append(s)


for i, n in enumerate(parent):
    if len(n) >= 2:
        parent[i] = check(n, parent)


for i in range(N):
    if len(parent[i]) == 0:
        parent[i] = 0
    else:
        parent[i] = parent[i][0]+1

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
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 dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s, dep):
    global ans
    global dist
    if dist[s] > dep:
        return
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t, dep + 1)


ans = [None] * N
dist = [0] * N
s = dfs1(0)
dfs2(s, 1)

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, m = [int(_) for _ in input().split()]
res_list = [-1] * n
b = []

ab_dict = {}
for i in range(n+m-1):
    ai, bi = [int(_) for _ in input().split()]
    b.append(bi)
    if not bi in ab_dict.keys():
        ab_dict[bi] = [ai]
    else:
        ab_dict[bi].append(ai)

testset = set([i for i in range(1, n+1)]) - set(ab_dict.keys())
par_list = [list(testset)[0]]
res_list[list(testset)[0]-1] = 0

while True:
    if len(ab_dict.keys()) == 0:
        break
    del_list = []
    for key, value in ab_dict.items():
        if res_list[key-1] == -1 and len(set(value) - set(par_list)) == 0:
            for i in range(len(par_list)-1, -1, -1):
                if par_list[i] in value:
                    res_list[key-1] = par_list[i]
                    break
            par_list.append(key)
            del_list.append(key)
    for del_key in del_list:
        del ab_dict[del_key]

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


def get_root(A):
    res = [A]
    search = [A]

    while(len(search) > 0):
        now = search.pop()
        for a in ans[now-1]:
            if a == 0:
                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 i, each_ans in enumerate(ans):

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

for line in new_ans:
    print(line)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(" "))
A,B = [0]*(N-1+M),[0]*(N-1+M)
edge = [ [] for _ in range(N) ]
par = [(-1,0)] * N
root = [0] * N
for i in range(N-1+M):
    A[i],B[i] = map(int,input().split(" "))
    edge[A[i]-1].append(B[i]-1)
    root[B[i]-1] = 1

que = []
for i in range(N):
    if root[i] == 0:
        par[i] = (0,0)
        que.append((i+1,0,0))
        break

while len(que) > 0:
    cur = que.pop()
    pos,prev,depth = cur
    for nx in edge[pos-1]:
        if par[nx][0] < depth+1:
            par[nx] = (depth+1,pos)
            que.append((nx+1,pos,depth+1))

for val,e in par:
    print(e)

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)}
root = [i for i in range(n)]
for _ in range(n-1+m):
    a,b = map(int, input().split())
    child[a-1].append(b-1)
    if b-1 in root:
        root.remove(b-1)

root = root[0]

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])
        if child[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:
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]
    else:
        return
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
for i in rank:
    print(i[1]+1)

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 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] += 1
node = 0
for i in range(1,N):
  if B[i] == 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):
    q.put(A[n][i])
    ans[A[n][i]] = n

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

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

import sys
sys.setrecursionlimit(200000)


def topological_sort(V, to):
    res = []
    cnt = [0] * V
    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]
        res.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return res


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.anc = set()
        self.children = set()


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:
    #     traverse(nodes[c])


order = topological_sort(N, to)

for i in order:
    traverse(nodes[i + 1])

invalid = set()
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:
def topological_sort(V, to):
    cnt = [0]*V
    s = []
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = [i for i in range(V) if cnt[i]==0]
    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 Counter

n, m = [int(_) for _ in input().split()]
res_list = [-1] * n
b = []

ab_dict = {}
for i in range(n+m-1):
    ai, bi = [int(_) for _ in input().split()]
    b.append(bi)
    if not bi in ab_dict.keys():
        ab_dict[bi] = [ai]
    else:
        ab_dict[bi].append(ai)

cou = Counter(b)

testset = set([i for i in range(1, n+1)]) - set(ab_dict.keys())
par_list = [list(testset)[0]]
res_list[list(testset)[0]-1] = 0

while True:
    if min(res_list) >= 0:
        break
    for key, value in ab_dict.items():
        if res_list[key-1] == -1 and len(set(value) - set(par_list)) == 0:
            for i in range(len(par_list)-1, -1, -1):
                if par_list[i] in value:
                    res_list[key-1] = par_list[i]
                    break
            par_list.append(key)

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

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)]
nnl2=np.array(nl2)
nnl22=nnl2.dot(nnl2)
nnl222=nnl22.dot(nnl2)
nnl2222=nnl222.dot(nnl2)
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 nnl22[j][i]>0 or nnl222[j][i]>0 or nnl2222[j][i]>0:
                     nl2[j][i]=0
                elif 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:
from collections import deque

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

root = root[0]

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:
N,M =[int(i)for i in input().split()]
oya =[[]for i in range(N)]
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]
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
for i in rank:
    print(i[1]+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
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 dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s):
    global ans
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t)


ans = [None] * N
dist = [0] * N
s = dfs1(0)
dfs2(s)

for x in ans:
    print(x)