Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from heapq import heappush,heapify,heappop
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

v = 0
while co[v]:
    v = co[v][0]

def dijkstra(s):
    prev = [-1] * n  # 経路復元
    INF = -(1 << 32)
    d = [INF] * n  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] > -p[0]:
            continue
        for e in es[v]:
            if d[e] < d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (-d[e], e)) 
                prev[e] = v
    return d, prev
_, parent = dijkstra(v)


for i in parent:
    print(i+1)

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]
    a = 0
    for i in co[v]:
        a = max(a, memo(i) + 1)
    dp[v] = a
    return a

for i in range(n):
    memo(i)

parent = [0] * n
for v in range(n):
    for e in es[v]:
        if dp[v] + 1 == dp[e]:
            parent[e] = v + 1

for i in parent:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque 
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

v = 0
while co[v]:
    v = co[v][0]

parent = [-1] * n
parent[v] = 0

q = deque([v])

while q:
    v = q.popleft()
    for e in es[v]:
        parent[e] = v + 1
        q.append(e)

for i in parent:
    print(i)

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]
    a = 0
    for i in co[v]:
        a = max(a, memo(i) + 1)
    dp[v] = a
    return a

for i in range(n):
    memo(i)

parent = [0] * n
for v in range(n):
    for e in es[v]:
        if dp[v] + 1 == dp[e]:
            parent[e] = v + 1

for i in parent:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque 
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

v = 0
while co[v]:
    v = co[v][0]

parent = [-1] * n
parent[v] = 0

q = deque([v])

while q:
    v = q.popleft()
    for e in es[v]:
        f = 1
        for p in co[e]:
            if parent[p] == -1:
                f = 0
                break
        if f:
            parent[e] = v + 1
            q.append(e)

for i in parent:
    print(i)

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
co = [[] for i in range(n)] # 有効辺の向きを逆にした
for i in range(n - 1 + m):
    a, b = map(int, input().split())    
    es[a - 1].append(b - 1)
    co[b - 1].append(a - 1)

dp = [-1] * n

def memo(v):
    if dp[v] != -1: #更新済
        return dp[v]
    a = 0
    for i in co[v]:
        a = max(a, memo(i) + 1)
    dp[v] = a
    return a

for i in range(n):
    memo(i)

parent = [0] * n
for v in range(n):
    for e in es[v]:
        if dp[v] + 1 == dp[e]:
            parent[e] = v + 1

for i in parent:
    print(i)