Problem p03142 (python)

Fixed submission:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

n,m = getNM()
children = [[] for i in range(n+2)]
n_in = [0] * (n+1)
par_origin = [0] * (n+1)

#入力の処理
for i in range(n+m-1):
    a,b = getNM()
    children[a].append(b)
    n_in[b] += 1

#根を見つける
for i in range(1,n+m-1):
    if n_in[i]:
        pass
    else:
        root = i
        break

#次数を減らしながら探索
import queue
def bfs(root):
    q = queue.Queue()
    q.put(root)
    while(True):
        try:
            cur = q.get(block=False)
        except:
            break
        for c in children[cur]:
            if n_in[c] == 1:
                par_origin[c] = cur
                q.put(c)
            else:
                n_in[c] -= 1

bfs(root)
for i in range(1, n+1):
    print(par_origin[i])

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 
 
def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD
 
 
def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD
 
 
def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret
 
 
def solve():
    n, m = getList()
    iri = [0 for i in range(n)]
    ki = [[] for i in range(n)]
 
    for i in range(n + m - 1):
        a, b = getZList()
        iri[b] += 1
        ki[a].append(b)
 
    root = -1
    for i, ir in enumerate(iri):
        if ir == 0:
            root = i
            break
 
    depth = [0 for i in range(n)]
    oya = [-1 for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root] = 1
    d = deque()
    d.append(root)
    while(d):
        cur = d.pop()
        cd = depth[cur]
        for nx in ki[cur]:
            if depth[nx] < cd + 1:
                depth[nx] = cd + 1
                oya[nx] = cur
 
            if not visited[nx]:
                d.append(nx)
 
            visited[nx] = 1
 
    for oy in oya:
        print(oy + 1)
 
 
 
def main():
    n = getN()
    for _ in range(n):
        solve()
 
 
if __name__ == "__main__":
    # main()
    solve()
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def solve():
    n, m = getList()
    iri = [0 for i in range(n)]
    ki = [[] for i in range(n)]

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

    root = -1
    for i, ir in enumerate(iri):
        if ir == 0:
            root = i
            break

    depth = [0 for i in range(n)]
    oya = [-1 for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root] = 1
    d = deque()
    d.append(root)
    while(d):
        cur = d.popleft()
        cd = depth[cur]
        for nx in ki[cur]:
            if depth[nx] < cd + 1:
                depth[nx] = cd + 1
                oya[nx] = cur

            if not visited[nx]:
                d.append(nx)

            visited[nx] = 1

    for oy in oya:
        print(oy + 1)



def main():
    n = getN()
    for _ in range(n):
        solve()


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

Buggy submission (verdict: Runtime Error):
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):
    for c in childs[n_cur]:
        d.append(c)
        dst[c] = max(dst[c], dst[n_cur]+1)
    while(d):
        bfs(d.pop())

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)

Buggy submission (verdict: Runtime Error):
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):)
    for c in childs[n_cur]:
        d.append(c)
        dst[c] = max(dst[c], dst[n_cur]+1)
    while(d):
        bfs(d.pop())

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)

Buggy submission (verdict: Runtime Error):
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.pop())


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)

Buggy submission (verdict: Runtime Error):
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()
class vertex():
    def __init__(self):
        self.number = 0
        self.dst = 0

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)
#vtxs = [vertex() for i in range(n+2)]
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)
    #print("d = {}".format(d))
    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)

Buggy submission (verdict: Runtime Error):
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()
class vertex():
    def __init__(self):
        self.number = 0
        self.dst = 0

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)
#vtxs = [vertex() for i in range(n+2)]
dst = [0 for i in range(n+1)]


d = deque()
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)
    #print("d = {}".format(d))
    while(d):
        bfs(d.popleft())

bfs(n_root)



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

Buggy submission (verdict: Runtime Error):
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()
class vertex():
    def __init__(self):
        self.number = 0
        self.dst = 0

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]
for i in range(m+n-1):
    m,n = getMN()
    parents[n].append(m)
    childs[m].append(n)
vtxs = [vertex() for i in range(n+2)]
dst = [0 for i in range(n+2)]
d = deque()
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)
    print("d = {}".format(d))
    while(d):
        bfs(d.popleft())

bfs(n_root)


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

Buggy submission (verdict: Runtime Error):
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()
class vertex():
    def __init__(self):
        self.number = 0
        self.dst = 0

parents = [[] for i in range(n+1)]
childs = [[] for i in range(n+1)]
for i in range(m+n-1):
    m,n = getMN()
    parents[n].append(m)
    childs[m].append(n)
vtxs = [vertex() for i in range(n+2)]
d = deque()
for i ,x in enumerate(parents[1:]):
    if not x:
        n_root = i+1
        break

vtxs[n_root].dst = 0


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

bfs(n_root)

dsts = (([v.dst for v in vtxs]))

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