Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
import heapq as hq
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ans
    for t in rg[s]:
        return dfs(t)
    else:
        ans[s] = 0
        return s


def bfs(s, dep):
    global ans
    global dist
    h = [[-dep, s]]
    while h:
        d, u = hq.heappop(h)
        if dist[u] > -d:
            continue
        for v in g[u]:
            if dist[v] <= dist[u] + 1:
                ans[v] = u + 1
                dist[v] = dist[u] + 1
                hq.heappush(h, [-(-d + 1), v])


ans = [None] * N
dist = [0] * N
s = dfs(0)
bfs(s, 0)

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
import heapq as hq
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ans
    for t in rg[s]:
        return dfs(t)
    else:
        ans[s] = 0
        return s


def bfs(s, dep):
    global ans
    global dist
    h = [[-dep, s]]
    while h:
        d, u = hq.heappop(h)
        if dist[u] > -d:
            continue
        for v in g[u]:
            if dist[v] <= dist[u] + 1:
                ans[v] = u + 1
                dist[v] = dist[u] + 1
                hq.heappush(h, [-(-d + 1), v])


ans = [None] * N
dist = [0] * N
s = dfs(0)
bfs(s, 0)

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s, dep):
    global ans
    global dist
    if dist[s] > dep:
        return
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t, dep + 1)


ans = [None] * N
dist = [0] * N
s = dfs1(0)
dfs2(s, 1)

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s, dep):
    global ans
    global dist
    if dist[s] < dep:
        return
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t, dep + 1)


ans = [None] * N
dist = [0] * N
s = dfs1(0)
dfs2(s, 0)

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s):
    global ans
    for t in g[s]:
        if dist[t] <= dist[s] + 1:
            ans[t] = s + 1
            dist[t] = dist[s] + 1
            dfs2(t)


ans = [None] * N
dist = [0] * N
s = dfs1(0)
dfs2(s)

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs1(s):
    global ans
    for t in rg[s]:
        return dfs1(t)
    else:
        ans[s] = 0
        return s


def dfs2(s):
    global ans
    for t in g[s]:
        if ans[t] is None:
            ans[t] = s + 1
            dfs2(t)


ans = [None] * N
s = dfs1(0)
dfs2(s)

for x in ans:
    print(x)


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)