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: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[[] for i in range(n+1)]
l=[list(map(int,input().split())) for i in range(n+m-1)]
for i in range(n+m-1):
    s[l[i][1]].append(l[i][0])
lis=[0 for _ in range(n)]
for i in range(1,n+1):
    lis[i-1]=len(s[i])
#print(s,lis)
for i in range(1,n+1):
    if lis[i-1]==0:
        print('0')
    elif lis[i-1]==1:
        print(s[i][0])
    else:
        ans=0
        cnt=0
        for j in range(lis[i-1]):
            a=lis[s[i][j]-1]
            #print(j,a)
            if cnt<a:
                ans=s[i][j]
                cnt=a
        print(ans)

Submission status: Wrong Answer

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]
    Kakutei = collections.defaultdict(lambda: False)

    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: Wrong Answer

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 and rs[m] != n:
            #print("+", l -1, m, n)
            ls[m] = l - 1
            rs[m] = n
            heappush(h, (l - 1, m, n))

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

Submission status: Wrong Answer

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

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

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b


from collections import deque

n, m = getMN()

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

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

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

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


def bfs(n_cur):
    #print(([v.dst for v in vtxs]))
    #c is pure integer
    #print("n_cur = {}".format(n_cur))
    for c in childs[n_cur]:
        d.append(c)
        #print("c = {}".format(c))
        dst[c] = max(dst[c], dst[n_cur]+1)
   
    #while(d):
    #    bfs(d.popleft())


bfs(n_root)

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

Submission status: Wrong Answer

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

high = [-1] * N
child = [set() for i in range(N)]
parent = [set() for i in range(N)]
res_p = [-1] * N
for s, v in links:
    s -= 1
    v -= 1
    parent[v].add(s)
    child[s].add(v)

def r_high(n):
    for c in child[n]:
        high[c] = max(high[n] + 1, high[c])


stack = []
for n, p in enumerate(parent):
    if len(p) == 0:
        res_p[n] = 0
        high[n] = 0
        r_high(n)
        stack.append(n)
        break


while stack:
    root = stack.pop(0)
    set_c = child[root]
    for c in set_c:
        parent[c] = {p for p in parent[c] if high[c] <= high[p] + 1}
        if len(parent[c]) == 1:
            res_p[c] = root + 1
            r_high(c)
            stack.append(c)

for r in res_p:
    print(r)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import Counter, defaultdict

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

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


# UnionFind
class UnionFind:
    # 負: ルートで値は木の深さを表す
    # 正: 子で値は次のノードを表す
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # 初期状態では全てのノードがルート

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  # グラフの高さが異なる場合
                # 木のランクが高い方のルートに併合させる
                # 併合後にランクの変動はない
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                # ランクが等しい木同士を併合させるので
                # 併合後は木のランクが1つ上がる
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x



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

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

# for key in T.keys():
#     print(key, T[key])

tree = defaultdict(int)
notleaf = set()
check = set()

uf = UnionFind(n)

for i in range(n):
    if i not in T.keys():
        tree[i + 1] = 0
        root = i
        notleaf.add(i)
        continue
    if len(T[i]) == 1:
        uf.unite(i, T[i][0])
        tree[i + 1] = T[i][0] + 1
        notleaf.add(i)

    check.add(i)
    for node in T[i]:
        notleaf.add(node)

# print(tree)
# print(T)

# print(uf.nodes)
used = set()
for i in range(n):
    if len(T[i]) > 1:
        for j in T[i]:
            if j not in used:
                break
        tree[i + 1] = j + 1
        used.add(j)

    # print('uf', i)
    # if uf.get_root(i) == i and uf.get_root(root) != i:
    #     print(i + 1, T[i])
    #     for j in T[i]:
    #         if j not in used:
    #             break
    #     print(i, j)
    #     tree[i + 1] = j + 1
    #     used.add(j)

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

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and  AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] <= 1:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    else:
        ans[tar:tar+1] = tmp[i][2][0:1]
        dic[tar] = -1
    i += 1

check = i
ch = 0
while ch < 2:
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = 0
            if dic[tar2] <= 0:
                if length <= abs(dic[tar2]):
                    length = abs(dic[tar2])
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1
    if max(dic.values()) <= 1:
        ch += 1

for a in ans[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and  AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] <= 1:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    else:
        ans[tar:tar+1] = tmp[i][2][0:1]
        dic[tar] = -1
    i += 1

check = i
ch = 0
while ch < 2:
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = 0
            if dic[tar2] <= 0:
                if length < abs(dic[tar2]):
                    length = abs(dic[tar2])
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1
    if max(dic.values()) <= 1:
        ch += 1

for a in ans[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
import queue

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

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

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


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


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


def main():
    n, m = get_int_list()
    A = []
    B = []
    for _ in range(n - 1 + m):
        a, b = get_int_list()
        A.append(a)
        B.append(b)

    root = (set(A) - set(B)).pop()
    graph = defaultdict(list)
    for a, b in zip(A, B):
        graph[a].append(b)
    known = {root}
    deq = deque([root])
    added = Counter()
    while sum(added) < m:
        parent = deq.popleft()
        children = graph[parent]
        for c in children:
            if c in known:
                added[c] += 1
                continue
            known.add(c)
            deq.append(c)
    parents = [0] * n
    deq = deque([root])
    cnt = 1
    while cnt < n:
        parent = deq.popleft()
        children = graph[parent]
        for c in children:
            if added[c] > 0:
                added[c] -= 1
                continue
            parents[c-1] = parent
            cnt += 1
            deq.append(c)
    for parent in parents:
        print(parent)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

seta = set()

ans = [0]*(n + 1)
top = ab[0]
for i in range(n + m - 1):
    if ab[i][1] not in seta:
        seta.add(ab[i][1])
        ans[ab[i][1]] = ab[i][0]
for i in range(1, n + 1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
N,M = [int(x) for x in input().split()]
li = [[0 for j in range(2)] for _ in range(N-1+M)]
output = [[] for _ in range(N)]
for i in range(N-1+M):
    li[i][0],li[i][1] = [int(x) for x in input().split()]
    output[li[i][1]-1].append(li[i][0])

for i in output:
    if(len(i)==0):
        print(0)
    else:
        print(i[0])

Submission status: Wrong Answer

Solution code:
import collections

N,M = map(int,input().split())
AB = []

for i in range(N-1+M):
    a,b = map(int,input().split())
    AB.append((b, a))

dic = collections.Counter(list(range(1,N+1)))

AB = sorted(AB)
tmp = []

ind = 0
for i in range(1,N+1):
    tmp2 = []
    num = 0
    while ind < N - 1 + M and  AB[ind][0] == i:
        tmp2.append(AB[ind][1])
        ind += 1
        num += 1
    tmp.append((num,i,tmp2))

tmp = sorted(tmp)

ans = [0 for _ in range(N+1)]

i = 0
while tmp[i][0] <= 1:
    tar = tmp[i][1]
    if tmp[i][0] == 0:
        ans[tar] = 0
        dic[tar] = 0
    else:
        ans[tar:tar+1] = tmp[i][2][0:1]
        dic[tar] = -1
    i += 1

check = i
while max(dic.values()) == 1:
    i = check
    while i < N:
        tar = tmp[i][1]

        for j in range(tmp[i][0]):
            tar2 = tmp[i][2][j]

            length = 0
            if dic[tar2] <= 0:
                if length < abs(dic[tar2]):
                    length = abs(dic[tar2])
                    ans[tar] = tar2
                    dic[tar] = -length

        i += 1

for a in ans[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
def solve():
    (N, M) = [int(x) for x in input().split()]
    graph = [list() for _ in range(N)]
    inv = [list() for _ in range(N)]
    for i in range(N-1+M):
        (u, v) = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        graph[u].append(v)
        inv[v].append(u)

    for u in range(N):
        while len(inv[u]) > 1:
            inv[u].pop()
        if len(inv[u])==1:
            inv[u] = inv[u][0]
        else:
            inv[u] = -1

    # print(inv)

    # graphviz
    # for u in range(N):
    #     if inv[u] >= 0:
    #         print("{} -> {}".format(inv[u]+1, u+1))

    for u in range(N):
        print(inv[u]+1)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

H = {}
F = [False] * (N+1)

for i in range(N-1+M):
    a, b = map(int, input().split())
    if F[a]  == False:
        H[a]  = [b]
        F[a]  = True
    else:
        H[a] += [b]

R = []

for root in H.keys():
    flag = True
    for leaf in H.keys():
        if root != leaf:
            if root in H[leaf]:
                flag = False
                break
    if flag:
        R.append(root)

assert len(R) == 1

for n in range(N):
    print(0)

Submission status: Wrong Answer

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)
used = [False] * (n+1)

def dfs(p, i, depth):
    if depth > D[i]:
        D[i] = depth
        P[i] = p
        if used[i]:
            return None
        used[i] = True
        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: Wrong Answer

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)
q = set([root])
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      if ans[c] == -1:
        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: Wrong Answer

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

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

prev = [-1] * N
search = [False] * N
v = [oya]
while v:
    now = v.pop(0)
    if search[now]:
        continue
    if G[now]:
        for u in G[now]:
            prev[u] = now
            v.append(u)
    search[now] = True

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(20000)

def dfs(temp):
    global dist, e, count_from, count_to
    global count, parent

    if count[temp] == count_from[temp]:
        for to in e[temp]:
            count[to] += 1
            temp_dist = dist[temp] + 1
            if temp_dist > dist[to]:
                parent[to] = temp
                dist[to] = temp_dist
            dfs(to)

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

count_from = [0] * N
count_to = [0] * N
e = [[] for _ in range(N)]

for i in range(N + M - 1):
    a, b = map(int, input().split())
    e[a - 1].append(b - 1)
    count_from[b - 1] += 1
    count_to[a - 1] += 1

start = 0
for i in range(N):
    if count_from[i] == 0:
        start = i
        break

dist = [0] * N
count = [0] * N
parent = [-1] * N

#dfs(start)

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
oya=[[] for i in range(n+1)]
ko=[[] for i in range(n+1)]
oya[0].append(0)
ko[0].append(0)
for i in range(n-1+m):
    a=[int(j) for j in input().split()]
    ab.append(a)
    oya[a[1]].append(a[0])
    ko[a[0]].append(a[1])
    
for i in range(n):
    l=[]
    p=0
    for j in oya[i+1]:
        q=0
        for k in oya[i+1]:
            if not k in ko[j]:
                q+=1
        if q==len(oya[i+1]):
            print(j)
            p=1
               
    if p==0:
        print(0)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))

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

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

if min(X) != 0:
    raise

Submission status: Wrong Answer

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

    print(1)

    # 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: Wrong Answer

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)
for i in range(1,N+1):
    print(distance[i])

Submission status: Wrong Answer

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]
parent_count = [0 for _ in range(N)]
for _ in range(N+M-1):
    A, B = list(map(int, input().split()))
    arr[A-1][B-1] = 1
    
for i in range(N):
    for j in range(N):
        parent_count[i] += arr[j][i]
    if parent_count[i] == 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
        if parent_count[i] > 1:
            arr[from_][to_] = 0
            parent_count[i] -= 1
            continue
        ans[to_] = from_+1
        queue.append(to_)
for a in ans:
    print(a)