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:
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
is_root = [False] + [True] * N
G = [[] for _ in range(N+1)]
for _ in range(N-1+M):
    A, B = map(int, input().split())
    G[A].append(B)
    is_root[B] = False
root = is_root.index(True)
queue = deque()
queue.append(root)
parent = [0] * (N+1)
while queue:
    u = queue.popleft()
    for v in G[u]:
        if parent[v] != u:
            parent[v] = u
            queue.append(v)
for i in range(1, N+1):
    print(parent[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N,M = map(int,input().split())
    edge = [[] for _ in range(N)]
    pcount = [0 for _ in range(N)]
    
    for _ in range(N-1+M):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        pcount[b-1] += 1

    for x,num in enumerate(pcount):
        if num == 0:
            root = x
            
    ans = [None for _ in range(N)]
    ans[root] = 0
    q = deque([root])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            pcount[fol] -= 1
            if pcount[fol] == 0:
                ans[fol] = now+1
                q.append(fol)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[y] == -1:
        now.append(y)
      pre[y] = x
print('\n'.join(map(lambda x: str(x+1) ,pre)))

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N-1+M)]

G = [set() for i in range(N)]
count = [0]*N
for a, b in(AB):
    a -= 1
    b -= 1
    G[a].add(b)
    count[b] += 1
root = 0
for i in range(N):
    if count[i] == 0:
        root = i
        break
level = [-1]*N
parent = [0]*(N)

q = collections.deque()
q.append(root)
while(q):
    x = q.popleft()
    l = level[x]
    for y in G[x]:
        if level[y] < l+1:
            if level[y] == -1:
                q.append(y)
            level[y] = l+1
            parent[y] = x+1


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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    edge_p = [[] for _ in range(N)]
    edge_n = [[] for _ in range(N)]
    for _ in range(N-1+M):
        a, b = (int(i)-1 for i in input().split())
        edge_p[a].append(b)
        edge_n[b].append(a)
    root = -1
    d = {}
    for i, es in enumerate(edge_n):
        if len(es) == 0:
            root = i  # 0-indexed
        d[i] = len(es)
    # print("root:", root)
    G_parent = ['NIL' for _ in range(N)]
    seen = [False]*(N)
    from heapq import heapify, heappop
    edge_p = [[(d[v], v) for v in es] for es in edge_p]
    for i in range(N):
        heapify(edge_p[i])

    def dfs(G, v):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            while len(G[u]):
                _, next_v = heappop(G[u])
                if seen[next_v]:
                    continue
                seen[next_v] = True
                G_parent[next_v] = u
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(edge_p, root)
    # print("parent:", G_parent)
    for p in G_parent:
        if p == "NIL":
            print(0)
        else:
            print(p+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
chl = [[] for _ in range(N)]
par = [[] for _ in range(N)]
for _ in range(N+M-1):
    a, b = map(int, input().split())
    chl[a-1].append(b-1)
    par[b-1].append(a-1)

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

from collections import deque
rnk = [-1]*N
q = deque([root])
rnk[root] = 0
while q:
    temp = q.popleft()
    for v in chl[temp]:
        if rnk[v] < 0:
            rnk[v] = rnk[temp]+1
            q.append(v)

ans = [0]*N
for i in range(N):
    p = -1
    for j in par[i]:
        if p < rnk[j]:
            p = rnk[j]
    s = set([])
    for j in par[i]:
        if rnk[j] == p:
            s.add(j)
    L = list(s)
    for j in L:
        if len(s & set(chl[j])) == 0:
            ans[i] = j+1
            break

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    edge_p = [[] for _ in range(N)]
    edge_n = [[] for _ in range(N)]
    for _ in range(N-1+M):
        a, b = (int(i)-1 for i in input().split())
        edge_p[a].append(b)
        edge_n[b].append(a)
    root = -1
    for i, es in enumerate(edge_n):
        if len(es) == 0:
            root = i  # 0-indexed
            break
    # print(root)
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(G, s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
            G_color[u] = 'BLACK'

    bfs(edge_p, root)
    for p in G_parent:
        if p == "NIL":
            print(0)
        else:
            print(p+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
visited = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  if visited[x] == 0:
    for y in tree_go[x]:
      que.append((y,x))
    visited[x] = 1
print(*parent[1:],sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1+m)]
tree_go = [[] for i in range(n+1)]
tree_come = [[] for i in range(n+1)]
for a,b in ab:
  tree_go[a].append(b)
  tree_come[b].append(a)
for i in range(1,n+1):
  if tree_come[i] == []:
    root = i
que = deque([(root,0)])
parent = [0 for i in range(n+1)]
visited = [0 for i in range(n+1)]
while que:
  x,px = que.popleft()
  parent[x] = px
  if visited[x] == 0:
    for y in tree_go[x]:
      que.append((y,x))
  visited[x] = 1
print(*parent[1:],sep="\n")

Submission status: Wrong Answer

Solution code:
from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

def main():
	n, m, *L = map(int, open(0).read().split())
	con = [[] for _ in range(n)]
	c = [True] * n
	for s, t in zip(*[iter(L)] * 2):
		con[s - 1] += [(t - 1, -1)]
		c[t - 1] = False
	for i in range(n):
		if c[i]:
			root = i
			break
	dist = Dijkstra(con, root)
	ans = [0] * n
	for s, t in zip(*[iter(L)] * 2):
		if dist[t - 1] + 1 == dist[s - 1]:
			ans[t - 1] = s
	print("\n".join(map(str, ans)))

if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:
from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[(t-1,-1)]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
dist=Dijkstra(con,root)
print(dist)
ans=[0]*n
for s,t in zip(*[iter(L)]*2):
	if dist[t-1]+1==dist[s-1]:
		ans[t-1]=s
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
edges = [[] for _ in range(n)]
cnt = [0]*n
for _ in range(n+m-1):
    a,b = LI()
    if cnt[b-1] > 0:
        continue
    edges[b-1].append(a-1)
    cnt[b-1] += 1

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

Submission status: Wrong Answer

Solution code:
def bfs(n,e,fordfs):
    P = [-1]*n
    que = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if P[ne] == -1:
                que.append(ne)
                P[ne] = now + 1
            else:
                P[ne] = now + 1
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
def bfs(n,e,fordfs):
    d = defaultdict(int)
    P = [-1]*n
    que = deque(); que2 = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if P[ne] == -1:
                que.append(ne)
                P[ne] = now + 1
            else:
                P[ne] = now + 1
                que2.append(ne)
    while que2:
        now = que2.pop()
        if d[now]:
            continue
        d[now] = True
        for ne in fordfs[now]:
            P[ne] = now + 1
            que2.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
def bfs(n,e,fordfs):
    d = defaultdict(int)
    P = [-1]*n
    que = deque(); que2 = deque()
    que.append(e)
    P[e] = 0
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if P[ne] == -1:
                que.append(ne)
                P[ne] = now + 1
            else:
                P[ne] = now + 1
                que2.append(ne)
    while que2:
        now = que2.popleft()
        if d[now]:
            continue
        d[now] = True
        for ne in fordfs[now]:
            P[ne] = now + 1
            que2.append(ne)
    return P
def examD():
    ans = 0
    N, M = LI()
    V = [[] for _ in range(N)]
    d = defaultdict(bool)
    for i in range(N+M-1):
        a, b = LI()
        #逆に張る
        V[a-1].append(b-1)
        d[b-1] = True
    for i in range(N):
        if not d[i]:
            start = i
            ans = bfs(N, start, V)
            break
    for v in ans:
        print(v)
#    print(V)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dic = {}
npflag = [True] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                

for i in range(N):

    print (p[i]+1)

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.pre = [None] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				self.pre[i] = v
				if self.visit[i] == "No":
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N, M = getlist()
	D = defaultdict(int)
	G = Graph()
	for i in range(N - 1 + M):
		A, B = getlist()
		G.add_edge(A - 1, B - 1)
		D[B - 1] += 1
	s = 0
	for i in range(N):
		if D[i] == 0:
			s = i
			break

	BF = BFS(G, s, N)
	ans = BF.pre
	for i in ans:
		if i == None:
			print(0)
		else:
			print(i + 1)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=[i]
while len(q)>0:
    u=q.pop()
    for v in g[u]:
        ans[v-1]=u+1
        q.append(v-1)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
for i in range(n):
    if len(g[i])==0:
        r=i
ans=[0]*n
q=[i]
while len(q)>0:
    u=q.pop()
    for v in g[u]:
        ans[v-1]=u+1
        q.append(v-1)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n, m = [ int(v) for v in input().split() ]
parent_check = [ 1 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
node_list = []
for i in range(n-1+m):
    a, b = [ int(v)-1 for v in input().split() ]
    node_list.append((a,b))
    connect_list[a].append(b)
    parent_check[b] = 0
parent_index = parent_check.index(1)

parent_list = [ None for i in range(n) ]
parent_list[parent_index] = -1

search_list = [parent_index]
while search_list != []:
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:
            if parent_list[j] is None:
                new_search_list.append(j)
            parent_list[j] = i
    search_list = new_search_list

for i in parent_list:
    print(i+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque



def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(node_num - 1 + edge_num)]

    parent_node = [0 for i in range(node_num + 1)]
    root_node = [1 for i in range(node_num + 1)]
    root_node[0] = 0
    graph_data = defaultdict(set)

    for i in range(node_num - 1 + edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        root_node[b] = 0

    root = -1
    for i in range(node_num + 1):
        if root_node[i]:
            root = i

    now_set = set()
    next_set = set()
    now_set.add(root)

    while len(now_set):
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                if parent_node[next_node] == 0:
                    next_set.add(next_node)
                parent_node[next_node] = now_node

        now_set = next_set
        next_set = set()

    for i in range(1, node_num + 1):
        print(parent_node[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m = map(int,input().split())
g = [set() for _ in range(n+1)]
gg = [0]*(n+1)
for _ in range(n-1+m):
  a,b = map(int,input().split())
  g[a].add(b)
  gg[b] = 1
p = [-1]*(n+1)
q = deque()
for i in range(1,n+1):
  if gg[i] == 0:
    p[i] = 0
    q.append(i)
    break
while q:
  v = q.popleft()
  for x in g[v]:
    if p[x] < 0:
      q.append(x)
    p[x] = v
for x in p[1:]:
  print(x)

Submission status: Wrong Answer

Solution code:
from collections import deque

def argt(arr):
    for i in range(len(arr)):
        if arr[i] is True:
            return i
    return len(arr)

N,M=map(int,input().split())
edges=[[] for _ in range(N)]
isroot=[True]*N

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

root = argt(isroot)
parents=[-1]*N
parents[root]=0
q = deque([root])
while q:
    src = q.popleft()
    for dst in edges[src]:
        if parents[dst] < 0:
            q.append(dst)
        parents[dst]=src+1
for p in parents:
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [False] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] = True
# print (lst)

ans_lst = [[0, -1] for _ in range(N)] #[距離, 親]を要素とするリスト
#根を求める = どこからも辺が伸びていないところ --> check_lst = Falseの場所
n = check_lst.index(False)
ans_lst[n][1] = -1
# print (n)

que = []
def dfs(i): #iからの経路を探す
    heappush(que, [0, i]) #最初の位置

    while len(que) != 0: #次に行けるところがある限り続ける
        #一番距離が遠くなるところを取り出す
        a = heappop(que) #a[0]: 距離、a[1]: 親
        for i in lst[a[1]]: #i: 有向グラフが繋がっていて次に行けるところ
            if ans_lst[i][0] <= -a[0] + 1: #距離をより長くできるとき
                ans_lst[i][0] = -a[0] + 1 #次に行くべきところの長さを更新
                ans_lst[i][1] = a[1] #次に行くべきところの親は今調べているところ
                heappush(que, [-(a[0] + 1), i])
    return 

dfs(n)
# print (ans_lst)

# print ('以下答え')
for d, i in ans_lst:
    print (i + 1)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [False] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] = True
# print (lst)

ans_lst = [[0, -1] for _ in range(N)] #[距離, 親]を要素とするリスト
#根を求める = どこからも辺が伸びていないところ --> check_lst = Falseの場所
n = check_lst.index(False)
ans_lst[n][1] = -1
# print (n)

que = []
def dfs(i): #iからの経路を探す
    heapq.heappush(que, [0, i]) #最初の位置

    while len(que) != 0: #次に行けるところがある限り続ける
        #一番距離が遠くなるところを取り出す
        a = heapq.heappop(que) #a[0]: 距離、a[1]: 親
        for i in lst[a[1]]: #i: 有向グラフが繋がっていて次に行けるところ
            if ans_lst[i][0] <= -a[0] + 1: #距離をより長くできるとき
                ans_lst[i][0] = -a[0] + 1 #次に行くべきところの長さを更新
                ans_lst[i][1] = a[1] #次に行くべきところの親は今調べているところ
                heapq.heappush(que, [-(a[0] + 1), i])
    return 

dfs(n)
# print (ans_lst)

# print ('以下答え')
for d, i in ans_lst:
    print (i + 1)

Submission status: Wrong Answer

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

L=[[]for i in range(N+1)]
p=[0 for i in range(N+1)]

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

for i in range(1,N+1):
    if p[i]==0:
        P=i
print(P)
p[P]=[0,0]
A=[]
for i in L[P]:
    A.append([i,P,1])
for i in range(10**6):
    if i==len(A):
        break
    else:
        p[A[i][0]]=[A[i][1],A[i][2]]
        for j in L[A[i][0]]:
            A.append([j,A[i][0],A[i][2]+1])
    #print(p)
    #print(A)
for i in range(1,N+1):
    print(p[i][0])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

L=[[]for i in range(N+1)]
p=[1 for i in range(N+1)]

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

B=0
for i in range(1,N+1):
    if p[i]==1:
        B=i
        break
#print(B)
P=[i for i in range(N+1)]
P[B]=0
A=[]
for i in range(len(L[B])):
    A.append([L[B][i],B])
#print(A)
for i in range(N+M-1):
    if i>=len(A):
        break
    else:
        P[A[i][0]]=A[i][1]
        for j in range(len(L[A[i][0]])):
            A.append([L[A[i][0]][j],A[i][0]])
    #print(A)
#print(P)
for i in range(1,N+1):
    print(P[i])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())

G=[]
C=[[] for i in range(n)]
B=[[] for i in range(n)]

for s in range(n+m-1):
    a,b=map(int,input().split())
    C[b-1].append(a)
    B[a-1].append(b)

root=C.index([])+1

S=[None for i in range(n)]
A=[]

S[root-1]=0
now=root
N=[now]
NextN=[]

while N != []:
    
    
    for r in range(len(N)):
        #print("N:",N)
        now=N.pop(0)
        if len(B[now-1]) >0:
            for q in B[now-1]:
                S[q-1]=now
            NextN.extend(B[now-1])
            B[now-1]=[]
            #print("S:",S)
    N.extend(NextN)
    NextN=[]
    """
    now=N.pop(0)
    A.append(now)
    for e in B[now-1]:
        C[e-1].remove(now)
        if C[e-1] == []:
            N.append(e)
"""

for ans in S:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def dfs(graph, nd, toprogy, is_visited):
    is_visited.add(nd)
    for adj in graph[nd]:
        if adj not in is_visited:
            dfs(graph, adj, toprogy, is_visited)

    toprogy.appendleft(nd)

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    graph = {}
    inv_graph = {}
    for i in range(1, N + 1):
        graph[i] = []
        inv_graph[i] = []

    for i in range(N - 1 + M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        graph[a].append(b)
        inv_graph[b].append(a)

    sys.setrecursionlimit(200000)
    toprogy = deque([])
    is_visited = set([])
    for i in range(1, N + 1):
        if i not in is_visited:
            dfs(graph, i, toprogy, is_visited)

    toprogical_order = {}
    for i in range(N):
        toprogical_order[toprogy[i]] = i + 1

    for i in range(1, N + 1):
        max_toprogy = 0
        true_parent = 0
        for pare in inv_graph[i]:
            if pare >= len(toprogical_order):
                continue
            if max_toprogy < toprogical_order[pare]:
                max_toprogy =toprogical_order[pare]
                true_parent = pare
        print true_parent

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,sys.stdin.readline().split()) 
al,bl=[],[]
for i in range(n+m-1):
    a,b=map(int,sys.stdin.readline().split())
    al += [a]
    bl += [b]
cnf = [i for i in range(1,n+1)]
ans = [0]*n

children = []
child = 0
for i in range(n):
    if len(children) == 0:        
        children = set(cnf)-set(bl)
        parent = child

    child = children.pop()
    
    j = 0
    while j < len(al):
        if al[j] == child:
            al.pop(j)
            bl.pop(j)
        else:
            j += 1
    ans[child-1] = parent
    cnf.remove(child)

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

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N + M - 1)]

# find start node
E = [[] for i in range(N)]
nE = [0] * N
for A, B in AB:
    E[A - 1].append(B)
    nE[B - 1] += 1

# print("#", E)
# print("#", nE)
    
S = []
for i in range(N):
    if nE[i] < 1: S.append(i + 1)

# print("#", S)
    
L = []
while len(S) > 0:
    Si = S.pop()
    L.append(Si)
    # print("##", Si)
    for Eij in E[Si - 1]:
        if nE[Eij - 1] == 1: S.append(Eij)
        nE[Eij - 1] -= 1
    # else:
    #     E[Si - 1] = []

# print("#", L)

# probably TLE...
ans = [0] * N
for i in range(N):
    for Eij in E[i]:
        # print("##", i + 1, Eij)
        if (i + 1) >= ans[Eij - 1]: ans[Eij - 1] = i + 1

for ansi in ans: print(ansi)

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

import sys
sys.setrecursionlimit(100000)

from collections import defaultdict

vs = defaultdict(set)

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

cache = {}

def calc(n):
    if n in cache:
        return cache[n]
    max_distance = 0
    max_distance_parent = 0
    for m in vs[n]:
        d = calc(m)[0]
        if max_distance < d + 1:
            max_distance = d + 1
            max_distance_parent = m
    result = max_distance, max_distance_parent
    cache[n] = result
    return result

for i in range(1, N + 1):
    print(i, calc(i))

Submission status: Wrong Answer

Solution code:
print(0)
print(1)
print(1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import numpy as np
import bisect


def is_input(node, path):
    for i in range(len(path)):
        if path[i][node]:
            return True
    return False


def topological_sort(path):
    S = []
    path = np.array(path)
    for i in range(len(path[0])):
        if any(path[:, i]):
            pass
        else:
            S.append(i)
    res = []
    path = path[:]
    while len(S) > 0:
        now = S.pop()
        res.append(now)
        for i, f in enumerate(path[now]):
            if f:
                path[now][i] = False
                if not is_input(i, path):
                    S.append(i)
    return res

N, M = map(int, input().split(" "))
path = [[False for i in range(N)] for i in range(N)]


for i in range(N+M-1):
    a, b = map(int, input().split(" "))
    path[a-1][b-1] = True

sorted_nodes = topological_sort(path)

input_nodes_list = [[] for i in range(N)]
for i, line in enumerate(path):
    temp = []
    for j, f in enumerate(line):
        if f:
            input_nodes_list[j].append(i)
ans = []
for input_nodes in input_nodes_list:
    if len(input_nodes) == 0:
        ans.append(0)
        continue
    if len(input_nodes) == 1:
        ans.append(input_nodes[0]+1)
        continue
    temp = 0
    temp_ans = input_nodes[0]
    for i in input_nodes:
        index = bisect.bisect_left(sorted_nodes, i)
        if index > temp:
            temp = index
            temp_ans = i
    ans.append(temp_ans+1)


for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys