Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02749 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

color = [-1] * n
def dfs(p, v, c):
    for nv in edge[v]:
        color[nv] = not c
        if nv == p:
            continue
        dfs(v, nv, not c)

dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
    white, black = black, white
    color = [not item for item in color]

# Fill 0 mod 3 or not
if white <= n // 3:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    others = [item for item in range(1, n+1) if item % 3 != 0]
    array = deque(others + threes)
# Fill 1 mod 3 or 2 mod 3
else:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    twos = [item for item in range(1, n+1) if item % 3 == 2]
    ones = [item for item in range(1, n+1) if item % 3 == 1]
    array = deque(ones + threes + twos)

ans = [-1] * n
for i, is_white in enumerate(color):
    if is_white:
        ans[i] = array.pop()
    else:
        ans[i] = array.popleft()

print(*ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

color = [-1] * n
def dfs(p, v, c):
    for nv in edge[v]:
        color[nv] = not c
        if nv == p:
            continue
        dfs(v, nv, not c)

dfs(-1, 0, 0)
white = sum(color)
black = n - white
if white > black:
    white, black = black, white
    color = [not item for item in color]

# Fill 0 mod 3 or not
if white <= n // 3:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    others = [item for item in range(1, n+1) if item % 3 != 0]
    array = deque(others + threes)
# Fill 1 mod 3 or 2 mod 3
else:
    threes = [item for item in range(1, n+1) if item % 3 == 0]
    twos = [item for item in range(1, n+1) if item % 3 == 2]
    ones = [item for item in range(1, n+1) if item % 3 == 1]
    array = deque(ones + threes + twos)

ans = [-1] * n
for i, is_white in enumerate(color):
    if is_white:
        ans[i] = array.pop()
    else:
        ans[i] = array.popleft()

print(*ans)
Problem p02803 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited = [[False] * w for _ in range(h)]
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[nx][ny] = True
print(ans)
Problem p02822 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)

childs = [[] for _ in range(n)]
def dfs(p, v):
    val = 1
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv)
        val += ret
        childs[v].append(ret)
    if val != n:
        childs[v].append(n - val)
    return val

dfs(-1, 0)
total_pattern = pow(2, n, MOD)
total_pattern_inv = pow(total_pattern, MOD-2, MOD)
inv2 = pow(2, MOD-2, MOD)
pow2_table = [1]
for i in range(2 * 10**5):
    pow2_table.append(pow2_table[-1] * 2 % MOD)
ans = 0
for line in childs:
    pattern_ok = 0
    if len(line) == 1:
        continue
    for item in line:
        pattern_ok += pow2_table[item] - 1
    pattern_ok += 1
    ans += (total_pattern * inv2 - pattern_ok) * total_pattern_inv
    ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)

childs = [[] for _ in range(n)]
def dfs(p, v):
    val = 1
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv)
        val += ret
        childs[v].append(ret)
    if val != n:
        childs[v].append(n - val)
    return val

dfs(-1, 0)
total_pattern = pow(2, n, MOD)
total_pattern_inv = pow(total_pattern, MOD-2, MOD)
inv2 = pow(2, MOD-2, MOD)
pow2_table = [1]
for i in range(10**5):
    pow2_table.append(pow2_table[-1] * 2 % MOD)
ans = 0
for line in childs:
    pattern_ok = 0
    if len(line) == 1:
        continue
    for item in line:
        pattern_ok += pow2_table[item] - 1
    pattern_ok += 1
    ans += (total_pattern * inv2 - pattern_ok) * total_pattern_inv
    ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)

childs = [[] for _ in range(n)]
def dfs(p, v):
    val = 1
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv)
        val += ret
        childs[v].append(ret)
    if val != n:
        childs[v].append(n - val)
    return val

dfs(-1, 0)
total_pattern = pow(2, n, MOD)
total_pattern_inv = pow(total_pattern, MOD-2, MOD)
inv2 = pow(2, MOD-2, MOD)
ans = 0
for line in childs:
    pattern_ok = 0
    if len(line) == 1:
        continue
    for item in line:
        pattern_ok += 2**item - 1
    pattern_ok += 1
    ans += (total_pattern * inv2 - pattern_ok) * total_pattern_inv
    ans %= MOD
print(ans)
Problem p02839 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MAX_VAL = 12800
 
h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))
 
# dp[height][width] bitset
dp = [[0] * (w+1) for _ in range(h+1)] 
delta = abs(a[0][0] - b[0][0])
dp[0][0] |= 1 << (MAX_VAL + delta)
dp[0][0] |= 1 << (MAX_VAL - delta)
for i in range(h):
    for j in range(w):
        diffr = abs(a[i][j+1] - b[i][j+1])
        diffd = abs(a[i+1][j] - b[i+1][j])
        # Move right
        add_delta = dp[i][j] << diffr
        sub_delta = dp[i][j] >> diffr
        dp[i][j+1] |= add_delta | sub_delta
        # Move down
        add_delta = dp[i][j] << diffd
        sub_delta = dp[i][j] >> diffd
        dp[i+1][j] |= add_delta | sub_delta
ans = MAX_VAL
for i in range(MAX_VAL * 2):
    if dp[h-1][w-1] & (1 << i):
        ans = min(ans, abs(i - MAX_VAL))
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MAX_VAL = 14000
OFFSET = MAX_VAL // 2

h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))

max_f = [[0] * (w+1) for _ in range(h+1)]
min_f = [[0] * (w+1 )for _ in range(h+1)]
# dp[height][width][bias]
dp = [[[0] * MAX_VAL for _ in range(w+1)] for _ in range(h+1)] 
max_f[0][0] = abs(a[0][0] - b[0][0])
min_f[0][0] = -abs(a[0][0] - b[0][0])

dp[0][0][OFFSET + a[0][0] - b[0][0]] = 1
dp[0][0][OFFSET + b[0][0] - a[0][0]] = 1
for i in range(h):
    for j in range(w):
        diffr = a[i][j+1] - b[i][j+1]
        diffd = a[i+1][j] - b[i+1][j]
        max_f[i][j+1] = max(max_f[i][j+1], max_f[i][j] + diffr)
        min_f[i][j+1] = min(min_f[i][j+1], min_f[i][j] - diffr)
        max_f[i+1][j] = max(max_f[i+1][j], max_f[i][j] + diffd)
        min_f[i+1][j] = min(min_f[i+1][j], min_f[i][j] - diffd)

        max_f[i][j+1] = min(OFFSET-10, max_f[i][j+1])
        min_f[i][j+1] = min(-OFFSET+10, min_f[i][j+1])
        max_f[i+1][j] = min(OFFSET-10, max_f[i+1][j])
        min_f[i+1][j] = min(-OFFSET+10, min_f[i+1][j])

        for k in range(OFFSET + min_f[i][j] - 1, OFFSET + max_f[i][j] + 1):
            if dp[i][j][k] == 0:
                continue
            # Move right
            dp[i][j+1][k+diffr] = 1
            dp[i][j+1][k-diffr] = 1
            # Move down
            dp[i+1][j][k+diffd] = 1
            dp[i+1][j][k-diffd] = 1
ans = 10**9
for i, item in enumerate(dp[h-1][w-1]):
    if item == 1:
        ans = min(ans, abs(i - OFFSET))
print(ans)
Problem p02840 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, x, d = [int(item) for item in input().split()]

if d == 0:
    if x == 0:
        print(1)
    else:
        print(n+1)
    exit()

range_in_kXmodD = dict() 
for i in range(0, n+1):
    kXmodD = i * x % d
    start = (i * x) // d + i * (i - 1) // 2
    end = (i * x) // d + i * (n - i + n - 1) // 2 + 1
    if kXmodD not in range_in_kXmodD:
        range_in_kXmodD[kXmodD] = []
    range_in_kXmodD[kXmodD].append((start, 1))
    range_in_kXmodD[kXmodD].append((end, -1))

ans = 0
for key in range_in_kXmodD.keys():
    range_in_kXmodD[key].sort()
    ret = 0
    cnt = 0
    prev = None 
    for val, c in range_in_kXmodD[key]:
        if prev != None and cnt > 0:
            ret += val - prev
        cnt += c
        prev = val
    ans += ret

print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, x, d = [int(item) for item in input().split()]
range_in_kXmodD = dict() 
for i in range(0, n+1):
    kXmodD = i * x % d
    start = (i * x) // d + i * (i - 1) // 2
    end = (i * x) // d + i * (n - i + n - 1) // 2 + 1
    if kXmodD not in range_in_kXmodD:
        range_in_kXmodD[kXmodD] = []
    range_in_kXmodD[kXmodD].append((start, 1))
    range_in_kXmodD[kXmodD].append((end, -1))

ans = 0
for key in range_in_kXmodD.keys():
    range_in_kXmodD[key].sort()
    ret = 0
    cnt = 0
    prev = None 
    for val, c in range_in_kXmodD[key]:
        if prev != None and cnt > 0:
            ret += val - prev
        cnt += c
        prev = val
    ans += ret

print(ans)
Problem p02926 (python)

Fixed submission:
import math
n = int(input())
xy = []
for i in range(n):
    x, y = [int(item) for item in input().split()]
    if x == 0 and y == 0:
        rad = 0.0
    elif x == 0:
        if y > 0:
            rad = math.pi / 2.0
        elif y < 0:
            rad = -math.pi / 2.0
    else:
        rad = math.atan2(y, x)
    deg = math.degrees(rad)
    xy.append((deg, x, y))

xy.sort()
xy2 = xy[:]
for i, (d, x, y) in enumerate(xy):
    xy2.append((d+360.0, x, y))
    if i == 0:
        xy2.append((d+720.0, x, y))
xy2.sort()

ans = 0.0
for i in range(n):
    for j in range(i+1, i+n+1):
        x = 0.0; y = 0.0
        for k in range(i, j):
            x += xy2[k][1]
            y += xy2[k][2]
        d = math.hypot(x, y)
        ans = max(ans, d)

print(ans)

Buggy submission (verdict: Runtime Error):
import math
n = int(input())
xy = []
for i in range(n):
    x, y = [int(item) for item in input().split()]
    if x == 0 and y == 0:
        continue
    elif x == 0:
        if y > 0:
            rad = math.pi / 2.0
        elif y < 0:
            rad = -math.pi / 2.0
    else:
        rad = math.atan2(y, x)
    deg = math.degrees(rad)
    xy.append((deg, x, y))

xy.sort()
xy2 = xy[:]
for d, x, y in xy:
    xy2.append((d+360.0, x, y))
    xy2.append((d+720.0, x, y))
xy2.sort()

l = 0; r = 1
    
ans = 0.0
while l < n:
    while xy2[r][0] - xy2[l][0] < 180.0:
        r += 1
    x = 0.0; y = 0.0
    for i in range(l, r):
        x += xy2[i][1]
        y += xy2[i][2]
    d = math.hypot(x, y)
    ans = max(ans, d)
    l += 1

print(ans)

Buggy submission (verdict: Runtime Error):
import math
n = int(input())
xy = []
for i in range(n):
    x, y = [int(item) for item in input().split()]
    if x == 0 and y == 0:
        continue
    elif x == 0:
        if y > 0:
            rad = math.pi / 2.0
        elif y < 0:
            rad = -math.pi / 2.0
    else:
        rad = math.atan2(y, x)
    deg = math.degrees(rad)
    xy.append((deg, x, y))

xy.sort()
xy2 = xy[:]
for d, x, y in xy:
    xy2.append((d+360.0, x, y))
xy2.append((xy[0][0] + 720.0, xy[0][1], xy[0][2]))

l = 0; r = 1
    
ans = 0.0
while l < n:
    while xy2[r][0] - xy2[l][0] < 180.0:
        r += 1
    x = 0.0; y = 0.0
    for i in range(l, r):
        x += xy2[i][1]
        y += xy2[i][2]
    d = math.hypot(x, y)
    ans = max(ans, d)
    l += 1

print(ans)
Problem p02937 (python)

Fixed submission:
import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------

input = sys.stdin.readline
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)
Problem p02949 (python)

Fixed submission:
INF = 10**18
n, m, p = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b, c = [int(item) for item in input().split()]
    a -= 1; b -= 1; c -= p
    c *= -1
    edge[a].append((b, c))
 
dist = [INF] * n
dist[0] = 0
update = 1
terminal_update = 0
for _ in range(n * 2):
    update = 0
    for v, e in enumerate(edge):
        for t, cost in e:
            if dist[v] != INF and dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                update = 1
                if t == n-1:
                    terminal_update += 1
    if not update:
        print(max(0, -dist[n-1]))
        exit()
else:
    if terminal_update > 1:
        print(-1)
    else:
        print(max(0, -dist[n-1]))

Buggy submission (verdict: Runtime Error):
INF = 10**10
 
def dfs(edge, visited, n):
    if visited[n]:
        return
    visited[n] = True
    for to, _ in edge[n]:
        dfs(edge, visited, to)

def bellman_ford(edge, mask):
    dist = [INF] * n
    dist[0] = 0

    for _ in range(n):
        update = False
        for i, es in enumerate(edge):
            if not mask[i]:
                continue
            for to, cost in es:
                if not mask[to]:
                    continue
                if dist[i] != INF and dist[i] + cost < dist[to]:
                    dist[to] = dist[i] + cost
                    update = True
        if not update:
            return dist
    else:
        # Found minus loops
        return -INF

if __name__ == "__main__":
    n, m, p = [int(item) for item in input().split()]
    edge = [[] for _ in range(n)]
    redge = [[] for _ in range(n)]
    for i in range(m):
        a, b, c = [int(item) for item in input().split()]
        a -= 1; b -= 1; c -= p
        c *= -1
        edge[a].append((b, c))
        redge[b].append((a, c)) 
    
    visited = [False] * n
    dfs(edge, visited, 0)
    rvisited = [False] * n
    dfs(redge, rvisited, n-1)
    mask = [forward and backward for forward, backward in zip(visited, rvisited)]
    dist = bellman_ford(edge, mask)
    if dist == -INF:
        print(-1)
    else:
        print(max(0, -dist[n-1]))
Problem p02976 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))

Buggy submission (verdict: Runtime Error):
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
vmap = dict()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
 
def dfs(prev, n):
    if prev < n:
        if (prev, n) in vmap:
            return 0 
        else:
            vmap[(prev, n)] = 1
    else:
        if (n, prev) in vmap:
            return 0 
        else:
            vmap[(n, prev)] = 1
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            print(n+1, v+1)
    if child_num % 2 == 0:
        return 1
    else:
        print(n+1, prev+1)
        return 0
 
dfs(-1, n // 2)
Problem p03026 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
ab = [[int(item) for item in input().split()] for _ in range(n-1)]
c = [int(item) for item in input().split()]
c.sort()
c.reverse()
sum_score = sum(c[1:])

edge = [[] for _ in range(n)]
score = [0] * n

for a, b in ab:
    a-=1; b-=1
    edge[a].append(b)
    edge[b].append(a)

it = 0
def dfs(f ,n):
    global it
    score[n] = c[it]
    it += 1
    for item in edge[n]:
        if item == f:
            continue
        dfs(n, item)
    return True

dfs(-1, 0)
print(sum_score)
print(" ".join([str(item) for item in score]))

Buggy submission (verdict: Runtime Error):
n = int(input())
ab = [[int(item) for item in input().split()] for _ in range(n-1)]
c = [int(item) for item in input().split()]
c.sort()
c.reverse()
sum_score = sum(c[1:])

edge = [[] for _ in range(n)]
score = [0] * n

for a, b in ab:
    a-=1; b-=1
    edge[a].append(b)
    edge[b].append(a)

it = 0
def dfs(f ,n):
    global it
    score[n] = c[it]
    it += 1
    for item in edge[n]:
        if item == f:
            continue
        dfs(n, item)
    return True

dfs(-1, 0)
print(sum_score)
print(" ".join([str(item) for item in score]))
Problem p03039 (python)

Fixed submission:
N, M, K = [int(item) for item in input().split()]
MOD = 10**9 + 7

n = 2 * 10**5 + 10
fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

total = 0
for i in range(M):
    total += (M - i) * N * N * mod_nCr(M * N - 2, K - 2) * i
    total %= MOD  
for i in range(N):
    total += (N - i) * M * M * mod_nCr(M * N - 2, K - 2) * i
    total %= MOD  
print(total)

Buggy submission (verdict: Runtime Error):
N, M, K = [int(item) for item in input().split()]
MOD = 10**9 + 7

n = 10*6 
fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

total = 0
for i in range(M):
    total += (M - i) * N * N * mod_nCr(M * N - 2, K - 2) * i
    total %= MOD  
for i in range(N):
    total += (N - i) * M * M * mod_nCr(M * N - 2, K - 2) * i
    total %= MOD  
print(total)
Problem p03044 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for i in range(n)]
colors = [0] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w%2])
    edge[v].append([u, w%2])

def dfs(frm, n, d):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            td = (d + tw) % 2
            if td == 1:
                colors[tv] = 1 
            else:
                colors[tv] = 0 
            dfs(n, tv, td)
    return True

colors[0] = 0
dfs(0, 0, 0)
for item in colors:
    print(item)

Buggy submission (verdict: Runtime Error):
n = int(input())
edge = [[] for i in range(n)]
colors = [-1] * n
for i in range(n-1):
    u, v, w = [int(item) for item in input().split()] 
    u -= 1
    v -= 1
    edge[u].append([v, w%2])
    edge[v].append([u, w%2])

def dfs(frm, n):
    for tv, tw in edge[n]:
        if tv == frm:
            continue
        else:
            if tw == 1:
                colors[tv] = (colors[frm] + 1) % 2
            else:
                colors[tv] = colors[frm]
            dfs(n, tv)

colors[0] = 0
dfs(0, 0)
for item in colors:
    print(item)