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:
# # E - League
# https://atcoder.jp/contests/abc139/tasks/abc139_e

from collections import defaultdict, deque

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

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

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

for r in res:
  print(r)

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
g = [[] for i in range(n+1)]
r = [[] for i in range(n+1)]
for i in range(n-1+m):
    a, b = map(int, input().split())
    g[a].append(b)
    r[b].append(a)


for i in range(1, n+1):
    if len(r[i]) == 0:
        root = i

ans = [0]*(n+1)
q = deque([root])
while q:
    now = q.popleft()
    for next in g[now]:
        if ans[next] == 0:
            q.append(next)
            ans[next] = now

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
        edges.pop(p)
    else:
        nex = []
    for n in nex:
        parent[n-1] = p
        que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
    else:
        nex = []
    for n in nex:
        if parent[n-1] == p:
            continue
        else:
            parent[n-1] = p
            que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
    else:
        nex = []
    for n in nex:
        if parent[n-1] == 0:
            parent[n-1] = p
            que.append(n)
        else:
            parent[n-1] = p
    if len(que) == 0:
        break

for p in parent:
    print(p)

Submission status: Wrong Answer

Solution code:
import queue
def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    par = [None]*(n+1)
    f = [True]*(n+1)
    for _ in range(n-1+m):
        a, b = map(int, input().split())
        G[a].append(b)
        f[b] = False
    p = -1
    for i in range(1, n+1):
        if f[i]:
            p = i
            break
    par[p] = 0
    q = queue.Queue()
    q.put(p)
    while not q.empty():
        x = q.get()
        for v in G[x]:
            if par[v] is None:
                q.put(v)
            par[v] = x
    for ans in par[1:]:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 有効グラフ上で、近道に当たる点はすべて余計な辺
# ある点に入ってくる最も距離が長い辺のみが有効となる
# DFSで、あとから入ってきたときにその親を記録すればよいのでは。
# 最後に残ったものを出力する
# 入力のあった頂点を記録することで、入力の無かった頂点を根とみなせる

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
G = [[] for i in range(N)]
grandparent = set(range(N))
for i in range(N - 1 + M):
  a,b = map(int,readline().split())
  G[a-1].append(b-1)
  grandparent -= {b - 1}

start = list(grandparent)[0]
from collections import deque

D = -1000
ans = [D for i in range(N)]

# 頂点、親
q = deque([[start, -1]])
while q:
  v, parent = q.popleft()
  prog = False
  if ans[v] == D:
    prog = True
  ans[v] = parent
  if not prog:
    continue
  for child in G[v]:
    q.append([child, v])
    
for a in ans:
  print(a + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
from collections import defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**60

class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)



class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def slv(S, T):
    lt = len(T)
    ls = len(S)
    SS = S * (-(-lt // ls) * 2 + 1)
    srh = RollingHash(SS, num=2)
    th = RollingHash(T, num=2).calc(0, len(T))

    ok = []
    for i in range(ls+lt):
        if srh.calc(i, i+lt) == th:
            ok.append(i)
    ok = set(ok)
    uf = UnionFind()
    for i in ok:
        if (i + lt) in ok:
            if not uf.union(i, (i+lt) % ls):
                return -1
    ans = 0
    for i in ok:
        ans = max(ans, uf.size(i))
    return ans



def main():
    S = input()
    T = input()
    print(slv(S, T))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
n,m=map(int,input().split())
s=set()
edge=[[] for _ in range(n)]
edgerev=[[] for _ in range(n)]
for _ in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edgerev[b].append(a)
    s.add(b)
for i in range(n):
    if i not in s:
        root=i
        break
visited=[False]*n
to=[] #topological order
def dfs(root):
    if visited[root]:
        return
    to.append(root)
    visited[root]=True
    for i in edge[root]:
        dfs(i)
dfs(root)
#print(to)
result=[0]*n
for i in range(n):
    result[to[i]]=i #頂点の順番
#print(result)
#print(edgerev)
for i in range(n):
    if not edgerev[i]:
        print(0)
        continue
    order=-1
    for j in edgerev[i]:
        if order<result[j]:
            ans=j
            order=result[j]
    print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
child = [set() for _ in range(n)]
parent = [set() for _ in range(n)]
root = set(range(n))

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

root = list(root)[0]
parent[root].add(-1)

que = deque([root])
d = [[-1,-1] for _ in range(n)]
d[root] = [0,-1]
while que:
    p = que.popleft()
    for nxt in child[p]:
        if d[nxt][1] == -1:
            d[nxt] = [d[p][0] + 1,p]
            que.append(nxt)
        elif d[nxt][0] > d[p][0] + 1:
            parent[nxt].remove(p)
        else:
            parent[nxt].remove(d[nxt][1])
            d[nxt][1] = p

for i in parent:
    print(list(i)[0] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
n,m=map(int,input().split())
ab = [[int(x) for x in input().split()] for _ in range(n-1+m)]
outs = defaultdict(list)
ins = defaultdict(int)

for v1,v2 in ab:
    outs[v1].append(v2)
    ins[v2]+=1 

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    def dfs(i,j):
        for e in edg[i]:
            if ans[e][1] >= j + 1 or ans[e][0] == i:
                continue
            dfs(e, j + 1)
            ans[e] = [i, j + 1]
    n, m = LI()
    edg = [[] for i in range(n)]
    rev_edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
        rev_edg[b].append(a)
    for i, e in enumerate(rev_edg):
        if len(e):
            continue
        root = i
        break
    ans = [[-1, 0]] * n
    dfs(root, 0)
    print("\n".join(map(str, map(lambda x: x[0] + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            d[t] = 1
            ans[t] = i
            q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if d[e]:
                    edg[i].remove(e)
                    d[e] = 0
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def S(): return input().rstrip()


def LS(): return S().split()


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                ans[e] = p
                if d[e]:
                    continue
                d[e] = 1
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        for t in edg[i]:
            if ans[t] == -1:
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if ans[e] == p:
                    continue
                ans[e] = p
                q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if ans[e] == -1:
                    d[e] = 1
                    ans[e] = p
                    q.append(e)
                else:
                    if d[e]:
                        ans[e] = p
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if ans[e] == p:
                    continue
                if ans[e] == -1:
                    d[e] = 1
                    ans[e] = p
                    q.append(e)
                else:
                    if d[e]:
                        ans[e] = p
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        d = defaultdict(int)
        for t in edg[i]:
            if ans[t] == -1:
                d[t] = 1
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if ans[e] == p:
                    continue
                if ans[e] == -1:
                    d[e] = 1
                    ans[e] = p
                    q.append(e)
                else:
                    if d[e]:
                        ans[e] = p
                        q.append(e)
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    a = m
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        for t in edg[i]:
            if ans[t] == -1:
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if ans[e] == p:
                    continue
                if ans[e] == -1:
                    ans[e] = p
                    q.append(e)
                else:
                    a -= 1
                    ans[e] = p
                if a:
                    continue
                break
            if a:
                continue
            break
        if a:
            continue
        break
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m = LI()
    a = m
    edg = [[] for i in range(n)]
    for i in range(n + m - 1):
        a, b = LI_()
        edg[a].append(b)
    ans = [-1] * n
    for i in range(n):
        q = deque()
        for t in edg[i]:
            if ans[t] == -1:
                ans[t] = i
                q.append(t)
        while q:
            p = q.popleft()
            for e in edg[p]:
                if ans[e] == p:
                    continue
                if ans[e] == -1:
                    ans[e] = p
                    q.append(e)
                else:
                    edg[ans[e]].remove(e)
                    a -= 1
                    ans[e] = p
                if a:
                    continue
                break
            if a:
                continue
            break
        if a:
            continue
        break
    print("\n".join(map(str, map(lambda x: x + 1, ans))))

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import collections

N, M = map(int, input().split())
T1 = [[] for _ in range(N)]
T2 = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    a, b = map(int, input().split())
    T1[a - 1].append(b - 1)
    T2[b - 1].append(a - 1)
for i in range(N):
    if T2[i] == []:
        r = i
        break

F = [-1 for _ in range(N)]
F2 = [0 for _ in range(N)]
que = collections.deque([[r, 0]])
while que:
    target, dis = que.pop()
    for d in T1[target]:
        if F2[d] == 0:
            F[d] = target
            F2[d] = dis + 1
            que.append([d, dis + 1])
        else:
            if dis + 1 > F2[d]:
                F[d] = target
                F2[d] = dis + 1

for i in range(N):
    F[i] += 1
print("\n".join(map(str, F)))

Submission status: Wrong Answer

Solution code:
import collections

N, M = map(int, input().split())
T1 = [[] for _ in range(N)]
T2 = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    a, b = map(int, input().split())
    T1[a - 1].append(b - 1)
    T2[b - 1].append(a - 1)
for i in range(N):
    if T2[i] == []:
        r = i
        break

F = [-1 for _ in range(N)]

que = collections.deque([r])
while que:
    target = que.popleft()
    for d in T1[target]:
        if F[d] == -1:
            F[d] = target
            que.append(d)
        else:
            F[d] = target

for i in range(N):
    F[i] += 1
print("\n".join(map(str, F)))

Submission status: Wrong Answer

Solution code:
import heapq as h
import sys

input=sys.stdin.readline


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

root=-1
for i in range(0,N):
    if fr[i]==[]:
        root=i
        break


parent=[-1 for i in range(0,N)]
q=[]
q.append(root)
h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in to[x]:
            if parent[p]==-1:
                h.heappush(sub,p)
                parent[p]=x
            else:
                parent[p]=x
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M = MI()

nl = [list() for _ in range(N + 1)]
rev = [list() for _ in range(N + 1)]
for _ in range(N - 1 + M):
    A, B = MI()
    nl[A].append(B)
    rev[B].append(A)

for i, l in enumerate(rev):
    if i > 0 and len(l) == 0:
        root = i
        break



ans = [-1] * (N + 1)
q = deque([(root, 0)])
while len(q) > 0:
    v, p = q.popleft()
    if ans[v] < 0:
        for next_v in nl[v]:
            q.append((next_v, v))
    ans[v] = p

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

Submission status: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1+M)]
data=[[] for i in range(N+1)]
lst=set()
for a,b in AB:
    data[a].append(b)
    lst.add(b)

st=list(set(range(1,N))-lst)[0]
exit()
stack=deque([st])
lst=[0 for i in range(N+1)]
while stack:
    a=stack.popleft()
    for p in data[a]:
        lst[p]=a
        stack.append(p)

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