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:
# -*- 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):
    """
    child : int
    """
    all_parents = []
    for p in to_par[child]:
        all_parents.append(p)
        all_parents.extend(find_all_parents(p))
    all_parents = list(set(all_parents))
    return all_parents


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:
from copy import deepcopy
N, M = [int(a) for a in input().split()]
# N, M = 6, 3
all_list = list()
for i in range(N):
    all_list.append([[], []])
# inputs = ["2 1", "2 3", "4 1", "4 2", "6 1", "2 6", "4 6", "6 5"]
for i in range(N + M - 1):
    a, b = [int(a) for a in input().split()]
    all_list[b-1][0].append(a)
    all_list[b-1][1].append(a)
    if len(all_list[b-1][0]) > 1:
        dummy_parent = deepcopy(all_list[b-1][0])
        for parent in dummy_parent:
            for other_parent in all_list[parent-1][0]:
                if parent != other_parent and other_parent in all_list[parent-1][1]:
                    try:
                        all_list[b-1][0].remove(other_parent)
                    except:
                        pass
    for dup in all_list:
        if a in dup[0] and b in dup[0]:
            dup[0].remove(a)
    # print(all_list)
for i in range(N):
    try:
        print(str(all_list[i][0][0]))
    except:
        print("0")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
xs = {}
used = [0] * N
for i in range(N+M-1):
  a, b = map(int, input().split())
  used[b-1] = 1
  if a in xs:
  	xs[a].append(b)
  else:
    xs[a] = [b]
 
root = used.index(0)+1
queue = deque([root])
while queue:
  c = queue.popleft()
  if c in xs:
    for x in xs[c]:
      used[x-1] = c
      queue.append(x)
 
for x in used:
  print(x)

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)
    d[b].append(a)
    ins[b] +=1
s = []
for i in range(n):
    if ins[i] == 0:
        s.append(i)
while s:
    x = s.pop(0)
    l.append(x)
    le = len(v[x])
    for i in range(le):
        y = v[x].pop(0)
        ins[y] -= 1
        if ins[y] == 0:
            s.append(y)
key = [l.index(i) for i in range(n)]
key.append(-1)
ans = [-1 for i in range(n)]
for i in range(n):
    if len(d[i]) != 0:
        ans[i] = n
        for j in d[i]:
            if key[j] > key[ans[i]]:
                ans[i] = 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:
from collections import defaultdict

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

A = defaultdict(list)
D = defaultdict(list)
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)
    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 len(D[s])>=2:
            D[s].remove(now)
        else:
            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:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1 + M)]

G = [set() for _ in range(N + 1)]
P_cand = [set() for _ in range(N + 1)]
for a, b in AB:
    G[a].add(b)
    P_cand[b].add(a)
for p in range(1, N):
    if len(P_cand[p]) == 0:
        break
D = [-1] * (N + 1)
P = [-1] * (N + 1)


def bfs(p):
    H = [[p, 0, 0]]
    while H:
        c, p, d = heapq.heappop(H)
        if D[c] < d:
            D[c] = d
            P[c] = p
            for c2 in G[c]:
                heapq.heappush(H, [c2, c, d + 1])


bfs(p)
[print(_) for _ in P[1:]]

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)

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

AB = [tuple(map(int, input().split())) for _ in range(N + M - 1)]
edge = [(a,b,-1) for a,b in AB ]
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d

class Tree:
    def __init__(self, n):
        self.parent = set()
        self.child = set()
        self.rank = -1
        self.current_parent = -1
        self.n = n

    def add_parent(self, i):
        self.parent.add(i)

    def add_child(self, i):
        self.child.add(i)

    def update_rank(self, v, parent_no):
        if self.rank >= v:
            return
        self.rank = v
        if self.current_parent != -1 and self.current_parent in self.parent:
            self.parent.remove(self.current_parent)
            trees[parent_no].child.remove(self.n)
        self.current_parent = parent_no
        for t in tuple(self.child):
            trees[t].update_rank(v + 1, self.n)

    def __repr__(self):
        return "child" + str(self.child) + "rank:" + str(self.rank) + " p:" + str(self.current_parent)


trees = [Tree(i) for i in range(N + 1)]
ans = [-1 for _ in range(N + 1)]
for a, b in AB:
    trees[a].add_child(b)
    trees[b].add_parent(a)

for i, t in enumerate(trees):
    if i != 0 and not t.parent:
        trees[0].add_child(i)
        trees[i].add_parent(0)
        edge.append((0,i,-1))
        break

a = (shortest_path(edge,N+1,0))

for t in trees[1:]:
    rank = a[t.n]
    for p in t.parent:
        if a[p] == rank+1:
            print(p)
            break

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
stack = [parent]
distance = [-1]*(N+1)
distance[parent] = 0
while stack:
    v = stack.pop()
    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:
def is_child(graph, start, goal):
    visited = {start}
    starts = {start}
    while True:
        nex = set()
        for s in starts:
            n = graph.get(s, set()) - visited
            if goal in n:
                return True
            nex = nex.union(n)
        if not nex:
            return False
        visited = visited.union(nex)
        starts = nex


def main():
    n, m = map(int, raw_input().split())
    graph = {}
    end = {}
    for _ in xrange(n - 1 + m):
        s, e = map(int, raw_input().split())
        if s not in graph:
            graph[s] = set()
        if e not in end:
            end[e] = []
        graph[s].add(e)
        end[e].append(s)
    for e, ss in end.items():
        if len(ss) <= 1:
            continue
        for s in ss:
            graph[s].remove(e)
        for s1 in ss:
            graph[s1].add(e)
            if any(s1 != s2 and not is_child(graph, s2, e) for s2 in ss):
                graph[s1].remove(e)
            else:
                break
    tree = [0] * n
    for s, ee in graph.items():
        for e in ee:
            tree[e - 1] = s
    for t in tree:
        print t


if __name__ == '__main__':
    main()

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)]
k = [[] for i in range(n)]
d = [[] for i in range(n)]
for a,b in c:
    v[a].append(b)
    k[b].append(a)
    d[b].append(a)
s = []
for i in range(n):
    if len(k[i]) == 0:
        s.append(i)
while s:
    x = s.pop(0)
    l.append(x)
    le = len(v[x])
    for i in range(le):
        y = v[x].pop(0)
        k[y].remove(x)
        if len(k[y]) == 0:
            s.append(y)
key = [l.index(i) for i in range(n)]
key.append(-1)
ans = [-1 for i in range(n)]
for i in range(n):
    if len(d[i]) != 0:
        ans[i] = n
        for j in d[i]:
            if key[j] > key[ans[i]]:
                ans[i] = 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 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)

    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 maybe_parent in Layer[i-1]:
                    A[l-1] = maybe_parent
                    Kakutei[l] = True
                    break
        
        i -= 1
    
    for a in A:
        print(a)


                


main()

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

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

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

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

from heapq import *

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 collections

def solve(N, M, AB):
    is_root = [1] * N
    parents = collections.defaultdict(list)
    children = collections.defaultdict(list)

    def bfs(root):
        distance = [-1] * N
        real_parent = {}
        que = [(root, -1, 0)]
        while que:
            n, p, d = que.pop(-1)
            if distance[n] < d:
                distance[n] = d
                real_parent[n] = p
                for c in children[n]:
                    que.append((c, n, d + 1))
        return real_parent

    for a1, b1 in AB:
        a = a1 - 1
        b = b1 - 1
        parents[b].append(a)
        children[a].append(b)
        is_root[b] = 0
    root = is_root.index(1)

    real_parent = bfs(root)
    return [real_parent[i] + 1 for i in range(N)]

if __name__ == '__main__':
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for i in range(N - 1 + M)]
    parents = solve(N, M, AB)
    for p in parents:
        print(p)

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

    # parent_nodes = [root]
    # i = 1
    # while len(parent_nodes) != 0:
    #     Layer.append([])
    #     new_parent_nodes = []

    #     j = 0
    #     while j < len(V):
    #         sv, ev = V[j]

    #         if sv in parent_nodes:
    #             Layer[i].append(ev)
    #             new_parent_nodes.append(ev)
            
    #         j += 1

    #     i += 1
    #     parent_nodes = new_parent_nodes

    Layer = Layer[:-1]
    Kakutei = []

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

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


                


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

sys.setrecursionlimit(300000)

N, M = ln()

parent = collections.defaultdict(list)
child = collections.defaultdict(list)

for i in xrange(N - 1 + M):
    a, b = ln()
    parent[b].append(a)
    child[a].append(b)

for x in child:
    random.shuffle(child[x])

top = 1
while parent[top]:
    top = parent[top][0]

unique_root = [0] * (N + 1)
v_depth = [0] * (N + 1)

def f(cur, depth, prev):
    unique_root[cur] = prev
    v_depth[cur] = depth
    for c in child[cur]:
        if v_depth[c] < depth + 1:
            f(c, depth + 1, cur)

f(top, 0, 0)

print '\n'.join(map(str, unique_root[1:]))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(" "))
A,B = [0]*(N-1+M),[0]*(N-1+M)

rev = [ [] for _ in range(N) ]
par = [(-1,0)] * N

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

for i in range(N):
    if len(rev[i]) == 0:
        par[i] = (0,0)
        break

while True:
    cnt = 0
    for i in range(N):
        if par[i][0] != -1:
            cnt += 1
            continue
        p = -1
        dep = -1
        flg = False
        for nx in rev[i]:
            if par[nx][0] == -1:
                flg = True
                break
            if dep < par[nx][1]+1:
                p = nx+1
                dep = par[nx][1]+1
            
        if not flg:
            par[i] = (p,dep)
    
    if cnt == N:
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 5 + 100)

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
root = set(range(n))
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    root.discard(b)
root = root.pop()

parents = [-1] * n
q = deque([(root, -1)])

while q:
    v, p = q.popleft()
    parents[v] = p
    q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in parents))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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

oriented = [[] for i in range(N)]
or_cop = [[] for i in range(N)]
oriented_num=[0 for i in range(N)]
oriented_tf = [False for i in range(N)]
to = [[] for i in range(N)]
to_num=[0 for i in range(N)]

for i in range(N-1+M):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    oriented[b].append([a,to_num[a]])
    or_cop[b].append([a,to_num[a]])
    to[a].append([b,oriented_num[b]])
    oriented_num[b]+=1
    to_num[a]+=1
    oriented_tf[b]=True

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

q = Queue()
q.put(root)
L = []

while not q.empty():
    v=q.get()
    L.append(v)
    for i in range(len(to[v])):
        m=to[v][i][0]
        d=to[v][i][1]
        to[v][i][0]=-1
        oriented[m][d][0]=-1
        flag=True
        for u in oriented[m]:
            if u[0]!=-1 and u[0]!=v:
                flag=False
                break
        if flag:
            q.put(m)

LL= [[L[i],i] for i in range(N)] 

LL=sorted(LL,key=lambda x: x[0])

for i in range(N):
    i_max=-1
    pare = -1
    if i==root:
        print(0)
    else:
        for cand in or_cop[i]:
            if LL[cand[0]][1]>i_max:
                i_max=LL[cand[0]][1]
                pare=cand[0]
        print(pare+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
C = [[] for i in range(N)]
P = [0] * N
for i in range(N - 1 + M):
  a, b = map(int, input().split())
  C[a - 1].append(b - 1)
  P[b - 1] -= 1
for i in range(N):
  if P[i] == 0:
    Q = [i]
    break
while Q:
  q = Q.pop(0)
  for c in C[q]:
    P[c] += 1
    if P[c] == 0:
      P[c] = q + 1
      Q.append(c)
for p in P:
  print(p)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
xs = {}
used = [0] * N
for i in range(N+M-1):
  a, b = map(int, input().split())
  used[b-1] = 1
  if a in xs:
  	xs[a].append(b)
  else:
    xs[a] = [b]
 
root = used.index(0)+1
queue = [root]
visited = []
while queue:
  c = queue.pop(0)
  if c in visited:
    continue
  visited.append(c)
  if c in xs:
    for x in xs[c]:
      used[x-1] = c
      queue.append(x)
 
for x in used:
  print(x)

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])
while vNows:
    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:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

sys.setrecursionlimit(300000)

N, M = ln()

parent = collections.defaultdict(list)
child = collections.defaultdict(list)

for i in xrange(N - 1 + M):
    a, b = ln()
    parent[b].append(a)
    child[a].append(b)

top = 1
while parent[top]:
    top = parent[top][0]

unique_root = [0] * (N + 1)
v_depth = [0] * (N + 1)

def f(cur, depth, prev):
    unique_root[cur] = prev
    v_depth[cur] = depth
    for c in child[cur]:
        if v_depth[c] < depth + 1:
            f(c, depth + 1, cur)

f(top, 0, 0)

print '\n'.join(map(str, unique_root[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue

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

tree = [[] for i in range(n)]
for x in t:
  tree[x[0]-1].append(x[1]-1)

not_root = set()
for u in tree:
  not_root = not_root | set(u)

rootset = set(range(n)) - not_root
root = rootset.pop()

parent = [-2] * n
parent[root] = -1
q = queue.Queue()
q.put(root)
while not q.empty():
  j = q.get()
  for x in tree[j]:
    parent[x] = j
    q.put(x)

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