Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)

Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
m = ab[-1][0]
dp = [0] * (m + t)
for a, b in ab:
    for j in range(t - 1, -1, -1):
        dp[a + j] = max(dp[a + j], dp[j] + b)
print(max(dp))

Fixed submission:
n, t = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
m = ab[-1][0]
dp = [0] * (m + t)
for a, b in ab:
    for j in range(t - 1, -1, -1):
        dp[a + j] = max(dp[a + j], dp[j] + b)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)

Fixed submission:
def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)
Buggy python submission (verdict: Runtime Error):
def search(i, cnt):
    if i <= n - 2 and h[i] >= h[i + 1]:
        search(i + 1, cnt + 1)
    else:
        li.append(cnt)
n = int(input())
h = list(map(int, input().split()))
li = []
for j in range(n):
    search(j, 0)
print(max(li))

Fixed submission:
n = int(input())
h = list(map(int, input().split()))
cnt = 0
l = []
for i in range(n - 1):
    if h[i] < h[i + 1]:
        l.append(cnt)
        cnt = 0
    else:
        cnt += 1
l.append(cnt)
print(max(l))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
print(sum(range(n)))

Fixed submission:
n = int(input())
print(n * (n - 1) // 2)
Buggy python submission (verdict: Runtime Error):
from math import sqrt
n = int(input())
cnt = 0
for i in range(1, n):
    for i in range(2, int(sqrt(n)) + 1):
        if i % j == 0:
            continue
    cnt += 1
print(cnt)

Fixed submission:
a = int(input())
s = input()
if a >= 3200:
    print(s)
else:
    print("red")

Buggy python submission (verdict: Runtime Error):
from math import sqrt
n = int(input())
cnt = 0
for i in range(1, n):
    for i in range(2, int(sqrt(n)) + 1):
        if i % j == 0:
            continue
    cnt += 1
print(cnt)

Fixed submission:
a = int(input())
s = input()
if a >= 3200:
    print(s)
else:
    print("red")
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()
if set(t) & set(s) == set(t):
    n = -1
    c = 0
    for i in t:
        try:
            n = list(s)[n + 1:].index(i) + n + 1
        except:
            n = -1
        if n == -1:
            c += 1
            try:
                n = list(s).index(i)
            except:
                n = -1
    print(n + len(s) * c + 1)
else:
    print(-1)

Fixed submission:
s = input()
t = input()
if set(t) & set(s) == set(t):
    n = -1
    c = 0
    for i in t:
        n = s.find(i, n + 1)
        if n == -1:
            c += 1
            n = s.find(i)
    print(n + len(s) * c + 1)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()
if set(t) & set(s) == set(t):
    n = -1
    c = 0
    for i in t:
        try:
            n = list(s)[n + 1:].index(i) + n + 1
        except:
            n = -1
        if n == -1:
            c += 1
            try:
                n = list(s).index(i)
            except:
                n = -1
    print(n + len(s) * c + 1)
else:
    print(-1)

Fixed submission:
s = input()
t = input()
if set(t) & set(s) == set(t):
    n = -1
    c = 0
    for i in t:
        n = s.find(i, n + 1)
        if n == -1:
            c += 1
            n = s.find(i)
    print(n + len(s) * c + 1)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
while True:
    cnt = 0
    for i in range(n):
        m = b[(i - 1) % n] + b[(i + 1) % n]
        if 0 < m < b[i] and a[i] < b[i]:
            cnt += (b[i] - a[i]) // m
            b[i] -= (b[i] - a[i]) // m * m
    ans += cnt
    if cnt == 0:
        break
print(ans if a == b else -1)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
while True:
    cnt = 0
    for i in range(n):
        m = b[(i - 1) % n] + b[(i + 1) % n]
        if 0 < m < b[i] and a[i] < b[i]:
            cnt += (b[i] - a[i]) // m
            b[i] -= (b[i] - a[i]) // m * m
    ans += cnt
    if cnt == 0:
        break
print(ans if a == b else -1)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i < ind:
            ind = i
ans = ind * (2 ** min(k - 1, 100))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Fixed submission:
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i < ind:
            ind = i
ans = ind * (2 ** min(k - 1, 20))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i < ind:
            ind = i
ans = ind * (2 ** (k - 1))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Fixed submission:
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i < ind:
            ind = i
ans = ind * (2 ** min(k - 1, 20))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i > ind:
            ind = i
ans = ind * (2 ** (k - 1))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])

Fixed submission:
n, k = map(int, input().split())
s = input()
rev_s = s + s[::-1]
mido = "z" * n
for i in range(n + 1):
    if mido > rev_s[i:i + n]:
        mido = rev_s[i:i + n]
ind = float("inf")
for i in range(n):
    if mido[i] != mido[0]:
        if i < ind:
            ind = i
ans = ind * (2 ** min(k - 1, 20))
print((mido[0] * ans + mido[ind:ind + n - ans])[:n])
Buggy python submission (verdict: Time Limit Exceeded):
from math import *
def fa(n):
    l = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            l.append([i, cnt])

    if temp != 1:
        l.append([temp, 1])

    if l == []:
        l.append([n, 1])

    return l
s = int(input())
l = fa(s + 1)
print(0, 0, l[0][0], 1, 1, ceil(s / l[0][0]))

Fixed submission:
from math import ceil
s = int(input())
print(0, 0, 10 ** 9, 1, abs(s - ((10 ** 9) * ceil(s / 10 ** 9))), ceil(s / 10 ** 9))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int(input()) for i in range(n)]
MAX = max(a)
se = list(reversed(sorted(set(a))))[1]
for i in range(n):
    if a[i] == MAX:
        print(se)
    else:
        print(MAX)

Fixed submission:
n = int(input())
a = [int(input()) for i in range(n)]
MAX = max(a)
se = list(reversed(sorted(a)))[1]
for i in range(n):
    if a[i] == MAX:
        print(se)
    else:
        print(MAX)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for i in range(n)]
l = a
for i in range(n):
    m = a.pop(i)
    print(max(a))
    a.insert(i, m)

Fixed submission:
n = int(input())
a = [int(input()) for i in range(n)]
MAX = max(a)
se = list(reversed(sorted(a)))[1]
for i in range(n):
    if a[i] == MAX:
        print(se)
    else:
        print(MAX)
Buggy python submission (verdict: Runtime Error):
n = int(input())
if n == 1:
  p = int(input())
else:
  p = list(map(input().split()))
i = 1
cnt = 0
while i < len(p):
  if p[i] > p[i - 1] and p[i] < p[i + 1] :
    cnt += 1
  i += 1

Fixed submission:
n = int(input())
p = list(map(int, input().split()))
i = 1
cnt = 0
while i < len(p) - 1:
  l = sorted([p[i - 1], p[i], p[i + 1]])
  if l[1] == p[i]:
    cnt += 1
  i += 1
print(cnt)

Buggy python submission (verdict: Runtime Error):
n = int(input())
p = list(map(input().split()))
i = 1
cnt = 0
while i < len(p):
  if p[i] > p[i - 1] and p[i] < p[i + 1] :
    cnt += 1
  i += 1

Fixed submission:
n = int(input())
p = list(map(int, input().split()))
i = 1
cnt = 0
while i < len(p) - 1:
  l = sorted([p[i - 1], p[i], p[i + 1]])
  if l[1] == p[i]:
    cnt += 1
  i += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
from scipy.misc import comb
n, k = map(int, input().split())
for i in range(1, k + 1):
    print(int(comb(n- k + 1, i) * comb(k - 1, i - 1) % (10 ** 9 + 7)))

Fixed submission:
from scipy.misc import comb
n, k = map(int, input().split())
for i in range(1, k + 1):
    print(int(comb(n - k + 1, i, exact=True)) * comb(k - 1, i - 1, exact=True) % (pow(10, 9) + 7))
Buggy python submission (verdict: Runtime Error):
n = int(input())
edges = [[] for i in range(200000)]
for i in range(n):
    x, y = map(int, input().split())
    edges[x - 1].append(y + 99999)
    edges[y + 99999].append(x - 1)
ans = 0
visited = [0] * (200000)
cntx, cnty = 0, 0
def dfs(u):
    global cntx, cnty
    visited[u] = 1
    if u // 100000 >= 1:
        cnty += 1
    else:
        cntx += 1
    for i in edges[u]:
        if visited[i] == 0:
            dfs(i)
ans = -1 * n
for i in range(100000):
    if visited[i] == 0:
        cntx, cnty = 0, 0
        dfs(i)
        ans += cntx * cnty
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(200000)]
for i in range(n):
    x, y = map(int, input().split())
    edges[x - 1].append(y + 99999)
    edges[y + 99999].append(x - 1)
ans = 0
visited = [0] * (200000)
cntx, cnty = 0, 0
def dfs(u):
    global cntx, cnty
    visited[u] = 1
    if u // 100000 >= 1:
        cnty += 1
    else:
        cntx += 1
    for i in edges[u]:
        if visited[i] == 0:
            dfs(i)
ans = -1 * n
for i in range(100000):
    if visited[i] == 0:
        cntx, cnty = 0, 0
        dfs(i)
        ans += cntx * cnty
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy
mod = 10 ** 9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = [1 for i in range(m + 1)]
for i in s:
    ans2 = deepcopy(ans)
    cnt = 0
    for j in range(m):
        ans2[j] = (cnt + ans2[j]) % mod
        if i == t[j]:
            cnt = (cnt + ans[j]) % mod
    ans2[-1] = (cnt+ ans2[-1]) % mod
    ans = deepcopy(ans2)
print(ans[-1])

Fixed submission:
from copy import deepcopy
mod = 10 ** 9 + 7
n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
ans = [1 for i in range(m + 1)]
for i in s:
    ans2 = deepcopy(ans)
    cnt = 0
    for j in range(m):
        ans2[j] = (cnt + ans2[j]) % mod
        if i == t[j]:
            cnt = (cnt + ans[j]) % mod
    ans2[-1] = (cnt+ ans2[-1]) % mod
    ans = deepcopy(ans2)
print(ans[-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
cnt = 0
while True:
    if "ABC" in s:
        cnt += s.count("ABC")
        s = s.replace("ABC", "BCA")
    else:
        break
print(cnt)

Fixed submission:
s = input()
s = s.replace("BC", "X")
cnt, ans = 0, 0
for i in s:
    if i == "A":
        cnt += 1
    elif i == "X":
        ans += cnt
    else:
        cnt = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (2 * n + 2)
fi = [1] * (2 * n + 2)
for i in range(1, 2 * n + 2):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(n):
    ans += (comb(n + i - 1, i) * (pow(a * pow(a + b, mod - 2, mod), n, mod) * pow(b * pow(a + b, mod - 2, mod), i, mod) + pow(b * pow(a + b, mod - 2, mod), n, mod) * pow(a * pow(a + b, mod - 2, mod), i, mod)) * (n + i)) % mod
    ans %= mod
print(ans * 100 * pow(100 - c, mod - 2, mod) % mod)

Fixed submission:
n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (2 * n + 2)
fi = [1] * (2 * n + 2)
for i in range(1, 2 * n + 2):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(n):
    ans += (comb(n + i - 1, i) * (pow(a * pow(a + b, mod - 2, mod), n, mod) * pow(b * pow(a + b, mod - 2, mod), i, mod) + pow(b * pow(a + b, mod - 2, mod), n, mod) * pow(a * pow(a + b, mod - 2, mod), i, mod)) * (n + i)) % mod
    ans %= mod
print(ans * 100 * pow(100 - c, mod - 2, mod) % mod)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 1000003
fa = [1] * (2 * mod + 1)
fi = [1] * (2 * mod + 1)
for i in range(1, 2 * mod + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
q = int(input())
for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
        continue
    if x == 0 or n >= mod:
        print(0)
        continue
    x *= pow(d, mod - 2, mod)
    x %= mod
    ans = (fa[x + n - 1] * fi[x - 1] % mod) * pow(d, n, mod)
    ans %= mod
    print(ans)

Fixed submission:
mod = 1000003
fa = [1] * (2 * mod + 1)
fi = [1] * (2 * mod + 1)
for i in range(1, 2 * mod + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
q = int(input())
for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
        continue
    if x == 0 or n >= mod:
        print(0)
        continue
    x *= pow(d, mod - 2, mod)
    x %= mod
    ans = (fa[x + n - 1] * fi[x - 1] % mod) * pow(d, n, mod)
    ans %= mod
    print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
bc = sorted([list(map(int, input().split())) for i in range(m)], key=lambda x:x[1], reverse=True)
ans = 0
x, y = 0, 0
for i in range(n):
    if a[x] > bc[y][1] or y == m:
        ans += a[x]
        x += 1
    else:
        ans += bc[y][1]
        bc[y][0] -= 1
        if bc[y][0] == 0:
            y += 1
print(ans)

Fixed submission:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
bc = sorted([list(map(int, input().split())) for i in range(m)], key=lambda x:x[1], reverse=True)
ans = 0
x, y = 0, 0
for i in range(n):
    if y == m or a[x] > bc[y][1]:
        ans += a[x]
        x += 1
    else:
        ans += bc[y][1]
        bc[y][0] -= 1
        if bc[y][0] == 0:
            y += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
n, m, k = map(int, input().split())
ans = 0
c = nCr(n + m)
for i in range(n):
    ans += i * (n - i) * m * m
    ans %= mod
for i in range(m):
    ans += i * (m - i) * n * n
    ans %= mod
print(ans * c.comb(n * m - 2, k - 2) % mod)

Fixed submission:
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
n, m, k = map(int, input().split())
ans = 0
c = nCr(n * m)
for i in range(n):
    ans += i * (n - i) * m * m
    ans %= mod
for i in range(m):
    ans += i * (m - i) * n * n
    ans %= mod
print(ans * c.comb(n * m - 2, k - 2) % mod)
Buggy python submission (verdict: Runtime Error):
n = int(input())
uvw = [list(map(int, input().split())) for i in range(n - 1)]
d = [-1 for i in range(n)]
edge = [[] for i in range(n)]
for u, v, w in uvw:
    edge[u - 1].append((v - 1, w))
    edge[v - 1].append((u - 1, w))
def dfs(now, D):
    d[now] = D
    for i, j in edge[now]:
        if d[i] == -1:
            dfs(i, D + j)
dfs(0, 0)
for i in d:
    print(i % 2)

Fixed submission:
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
n = int(input())
uvw = [list(map(int, input().split())) for i in range(n - 1)]
d = [-1 for i in range(n)]
edge = [[] for i in range(n)]
for u, v, w in uvw:
    edge[u - 1].append((v - 1, w))
    edge[v - 1].append((u - 1, w))
def dfs(now, D):
    d[now] = D
    for i, j in edge[now]:
        if d[i] == -1:
            dfs(i, D + j)
dfs(0, 0)
for i in d:
    print(i % 2)
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        b2 = (n - (i * r + j * g)) / b
        if b2 >= 0 and b2 % 1 == 0:
            ans += 1
print(ans)

Fixed submission:
r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
    for j in range(n // g + 1):
        b2 = (n - (i * r + j * g)) / b
        if b2 >= 0 and b2 % 1 == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
que = []
v = [[True] * (w + 2)]
v += [[True] + [j == "#" for j in a[i]] + [True] for i in range(h)]
v.append([True] * (w + 2))
m = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if v[i][j]:
            que.append((i, j))
ans = 0
while que:
    p = []
    ans += 1
    for x, y in que:
        if not v[x - 1][y]:
            v[x - 1][y] = True
            p.append((x - 1, y))
        if not v[x + 1][y]:
            v[x + 1][y] = True
            p.append((x + 1, y))
        if not v[x][y - 1]:
            v[x][y - 1] = True
            p.append((x, y - 1))
        if not v[x][y + 1]:
            v[x][y + 1] = True
            p.append((x, y + 1))
    que = p
print(ans - 1)

Fixed submission:
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
que = []
v = [[True] * (w + 2)]
v += [[True] + [j == "#" for j in a[i]] + [True] for i in range(h)]
v.append([True] * (w + 2))
m = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if v[i][j]:
            que.append((i, j))
ans = 0
while que:
    p = []
    ans += 1
    for x, y in que:
        if not v[x - 1][y]:
            v[x - 1][y] = True
            p.append((x - 1, y))
        if not v[x + 1][y]:
            v[x + 1][y] = True
            p.append((x + 1, y))
        if not v[x][y - 1]:
            v[x][y - 1] = True
            p.append((x, y - 1))
        if not v[x][y + 1]:
            v[x][y + 1] = True
            p.append((x, y + 1))
    que = p
print(ans - 1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
l = []
b = 0
w = s.count(".")
for i in range(1, n - 1):
    if s[i - 1] == "#":
        b += 1
    elif s[i + 1] == ".":
        w -= 1
    l.append(b + w)
print(min(l))

Fixed submission:
n = int(input())
s = input()
b = 0
w = s.count(".")
l = [w]
for i in range(1, n + 1):
    if s[i - 1] == "#":
        b += 1
    if s[i - 1] == ".":
        w -= 1
    l.append(b + w)
print(min(l))

Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
l = []
b = 0
w = s.count(".")
for i in range(n):
    if s[i] == "#":
        b += 1
    elif s[i] == ".":
        w -= 1
        l.append(b + w)
print(min(l))

Fixed submission:
n = int(input())
s = input()
b = 0
w = s.count(".")
l = [w]
for i in range(1, n + 1):
    if s[i - 1] == "#":
        b += 1
    if s[i - 1] == ".":
        w -= 1
    l.append(b + w)
print(min(l))