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

Fixed submission:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    S = []

    d = [[float("inf")] * N for _ in range(N)]
    L = []
    for i in range(M):
        a, b, c = map(int, input().split())
        d[a - 1][b - 1] = c
        d[b - 1][a - 1] = c
        if a < b:
            L.append((a - 1, b - 1))
        else:
            L.append((b - 1, a - 1))
    for i in range(N):
        d[i][i] = 0
    L = set(L)

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

    warshall_floyd(d)
    print(len(set(S)))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    S = []

    d = [[float("inf")] * N for _ in range(N)]
    L = []
    for i in range(M):
        a, b, c = map(int, input().split())
        d[a - 1][b - 1] = c
        d[b - 1][a - 1] = c
        if a < b:
            L.append((a - 1, b - 1))
        else:
            L.append(b - 1, a - 1)
    for i in range(N):
        d[i][i] = 0
    L = set(L)

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

    warshall_floyd(d)
    print(len(set(S)))


if __name__ == "__main__":
    main()
Problem p03845 (python)

Fixed submission:
N=int(input())
T=list(map(int,input().split()))
M=int(input())
P=[]
X=[]
for k in range(M):
    p,x=map(int,input().split())
    P.append(p)
    X.append(x)

for h in range(M):
    time=sum(T)-T[P[h]-1]+X[h]
    print(time)

Buggy submission (verdict: Runtime Error):
N=int(input())
T=[int(i) for i in raw_input().split()]
M=int(input())

for i in range(M):
    p,x=map(int,raw_input().split())
    time=sum(T)-T[p-1]+x
    print(time)

Buggy submission (verdict: Runtime Error):
N=int(input())
T=[int(i) for i in raw_input().split()]
M=int(input())
PX=[]
for i in range(M):
    p,x=map(int,raw_input().split())
    time=sum(T)-T[p-1]+x
    print(time)

Buggy submission (verdict: Runtime Error):
N=int(input())
T=[int(i) for i in raw_input().split()]
M=int(input())
PX=[]
for i in range(M):
    PX.append([int(k) for k in raw_input().split()])
if N>=M:
    for h in range(M):
        time=sum(T)-(T[PX[h][0]-1]-PX[h][1])
        print(time)
else:
    for h in range(N):
        time=sum(T)-(T[PX[h][0]-1]-PX[h][1])
        print(time)

Buggy submission (verdict: Runtime Error):
N=int(input())
T=[int(i) for i in raw_input().split()]
M=int(input())
PX=[]
for i in range(M):
    PX.append([int(k) for k in raw_input().split()])

for h in range(M):
    time=sum(T)-(T[PX[h][0]-1]-PX[h][1])
    print(time)
Problem p03919 (python)

Fixed submission:
import sys
h,w=map(int,input().split())
A=[chr(i) for i in range(ord('A'), ord('Z')+1)]
s=[]
for i in range(h):
    s.append(list(map(str,input().split())))
for i in range(h):
    for j in range(w):
        if s[i][j]=='snuke':
            a=A[j]
            b=str(i+1)
            print(a+b)
            sys.exit()

Buggy submission (verdict: Runtime Error):
import sys
h,w=map(int,input().split())
A=['A','B','C','D','E','F','G','H','I','J']
s=[]
for i in range(h):
    s.append(list(map(str,input().split())))
for i in range(h):
    for j in range(w):
        if s[i][j]=='snuke':
            a=A[j]
            b=str(i+1)
            print(a+b)
            sys.exit()
Problem p04001 (python)

Fixed submission:
S=input()
n=len(S)
ans=0
for i in range(1<<(n-1)):
    k=0
    for j in range(n):
        if 1&(i>>j):
            ans+=int(S[k:j+1])
            k=j+1
    ans+=int(S[k:])
        
print(ans)

Buggy submission (verdict: Runtime Error):
S=input()
n=len(S)
ans=0
for i in range(1<<(n-1)):
    for j in range(n):
        if 1&(i>>j):
            ans+=int(S[k:j+1])
            k=j+1
    ans+=int(S[k:])
        
print(ans)
Problem p04015 (python)

Fixed submission:
n,a=map(int,input().split())
X=[int(i)-a for i in input().split()]

memo={0:1}
for x in X:
    for k,v in list(memo.items()):
        memo[x+k]=memo.get(x+k,0)+v
print(memo[0]-1)

Buggy submission (verdict: Runtime Error):
n,a=map(int,input().split())
X=[int(i)-a for i in input().split()]

memo={0:1}
for x in X:
    for k,v in list(memo.items()):
        memo[x+k]=memo.get(x+k,0)+v
        print(memo)
print(memo[0]-1)
Problem p04029 (python)

Fixed submission:
N=int(input())

print(int((N+1)*N/2))

Buggy submission (verdict: Runtime Error):
s=input()
S=list(s)
L=len(S)
A=[]
for i in range(L):
    if S[i]=='0' or S[i]=='1':
        A.append(S[i])
    elif S[i]=='B' and len(A)==0:
        A.append('')
    else:
        A.remove(A[-1])
a=''.join(A)
print(a)

Buggy submission (verdict: Runtime Error):
s=input()
S=list(s)
L=len(S)
A=[]
for i in range(L):
    if S[i]=='0' or S[i]=='1':
        A.append(S[i])
    elif S[i]=='B' and len(A)==0:
        A.append('')
    else:
        A.remove(A[-1])
a=''.join(A)
print(a)
Problem p02609 (python)

Fixed submission:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
X = input()

popcount = X.count('1')

def mod(popcount):
    if popcount in [0, 1]:
        return [0] * N
    a = []
    base = 1
    for i in range(N):
        if i == 0:
            a.append(1)
        else:
            base = base * 2 % popcount
            a.append(base)
    return a

def summod(modX, popcount):
    if popcount == 0:
        return 0
    a = 0
    for i, x in enumerate(modX):
        if X[i] == '1':
            a = (a + x) % popcount
    return a

modXm = list(reversed(mod(popcount - 1)))
modXp = list(reversed(mod(popcount + 1)))

s_modXm = summod(modXm, popcount - 1)
s_modXp = summod(modXp, popcount + 1)

for i in range(N):
    if X[i] == '1':
        if popcount - 1 == 0:
            print(0)
            continue
        modX, s, m = modXm, s_modXm, popcount - 1
        s = (s + m - modX[i]) % m
    else:
        modX, s, m = modXp, s_modXp, popcount + 1
        s = (s + modX[i]) % m
    ans = 1
    while True:
        pc = bin(s).count('1')
        if pc == 0:
            break
        s = s % pc
        ans += 1
    print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
X = input()

popcount = X.count('1')

def mod(popcount):
    if popcount == 1:
        return [0] * N
    a = []
    base = 1
    for i in range(N):
        if i == 0:
            a.append(1)
        else:
            base = base * 2 % popcount
            a.append(base)
    return a

def summod(modX, popcount):
    a = 0
    for i, x in enumerate(modX):
        if X[i] == '1':
            a = (a + x) % popcount
    return a

modXm = list(reversed(mod(popcount - 1)))
modXp = list(reversed(mod(popcount + 1)))

s_modXm = summod(modXm, popcount - 1)
s_modXp = summod(modXp, popcount + 1)

for i in range(N):
    if X[i] == '1':
        if popcount - 1 == 0:
            print(0)
            continue
        if popcount - 1 == 1:
            print(1)
            continue
        modX, s, m = modXm, s_modXm, popcount - 1
        s = (s + m - modX[i]) % m
    else:
        modX, s, m = modXp, s_modXp, popcount + 1
        s = (s + modX[i]) % m
    ans = 1
    while True:
        pc = bin(s).count('1')
        if pc == 0:
            break
        s = s % pc
        ans += 1
    print(ans)
Problem p02616 (python)

Fixed submission:
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

if all(a < 0 for a in A) and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for a in A[:K]:
        ans = ans * a % MOD
    print(ans)
    exit(0)

p = []
n = []
for a in A:
    if a < 0:
        heappush(n, a)
    else:
        heappush(p, -a)

ans = 1
cnt = 0
while cnt < K:
    if cnt == K - 1:
        if len(p) > 0:
            ans = ans * -heappop(p) % MOD
        else:
            ans = ans * max(n) % MOD
        cnt += 1
        break
    if len(p) < 1:
        ans = ans * heappop(n) * heappop(n) % MOD
        cnt += 2
    elif len(n) < 2:
        ans = ans * -heappop(p) % MOD
        cnt += 1
    else:
        p0, p1 = -p[0], -p[1] if len(p) > 1 else 1
        if p0 * p1 > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        else:
            ans = ans * heappop(n) * heappop(n) % MOD
            cnt += 2
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

if all(a < 0 for a in A) and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for a in A[:K]:
        ans = ans * a % MOD
    print(ans)
    exit(0)

p = []
n = []
for a in A:
    if a < 0:
        heappush(n, a)
    else:
        heappush(p, -a)

ans = 1
cnt = 0
while cnt < K:
    if cnt == K - 1:
        if len(p) > 0:
            ans = ans * -heappop(p) % MOD
        else:
            ans = ans * max(n) % MOD
        cnt += 1
        break
    if len(p) < 1:
        ans = ans * heappop(n) * heappop(n) % MOD
        cnt += 2
    elif len(n) < 2:
        ans = ans * -heappop(p) % MOD
        cnt += 1
    else:
        if len(p) < 2 and -p[0] > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        elif -p[0] * -p[1] > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        else:
            ans = ans * heappop(n) * heappop(n) % MOD
            cnt += 2
print(ans)
Problem p02618 (python)

Fixed submission:
import sys
sys.setrecursionlimit(300000)
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


D = I()
C = LMI()
S = [LMI() for _ in range(D)]

last = defaultdict(int)
ans = 0
for d in range(D):
    m = -INF
    ans = -1
    for i in range(26):
        lans = S[d][i]
        for j in range(26):
            if i == j:
                lans -= C[j] * (d + 1 - d - 1)
            else:
                lans -= C[j] * (d + 1 - last[j])
        if lans > m:
            m = lans
            ans = i
    print(ans + 1)

Buggy submission (verdict: Runtime Error):
from time import perf_counter
t0 = perf_counter()


import sys
sys.setrecursionlimit(300000)
from collections import defaultdict
from random import randint

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


D = I()
C = LMI()
S = [LMI() for _ in range(D)]


# 初期解の生成
ans0 = []
for d in range(D):
    ans0.append(d % 26 + 1)

T = ans0
last = [[i + 1] * 26 for i in range(D)]
for d in range(D):
    i = T[d]
    j = 0
    for dd in range(d, D):
        last[dd][i] = j
        j += 1

def eval(d, q):
    i = T[d]
    val = S[d][q] - S[d][i]

    contrib = 0
    if d == 0:
        j = 1
    else:
        j = last[d - 1][i] + 1
    for dd in range(d, D):
        if dd > d and last[dd][i] == 0:
            break
        contrib += j - last[dd][i]
        # last[dd][i] = j
        j += 1
    val -= contrib * C[i]

    contrib = 0
    j = 0
    for dd in range(d, D):
        if last[dd][q] == 0:
            break
        contrib += last[dd][q] - j
        # last[dd][q] = j
        j += 1
    val += contrib * C[q]

    # T[d] = q

    return val

def apply(d, q):
    i = T[d]

    if d == 0:
        j = 1
    else:
        j = last[d - 1][i] + 1
    for dd in range(d, D):
        if dd > d and last[dd][i] == 0:
            break
        last[dd][i] = j
        j += 1

    j = 0
    for dd in range(d, D):
        if last[dd][q] == 0:
            break
        last[dd][q] = j
        j += 1

    T[d] = q

i = 0
while perf_counter() - t0 < 1.8:
    d = randint(0, D - 1)
    q = randint(0, 25)
    if eval(d, q) > 0:
        apply(d, q)
    else:
        if randint(0, (i + 1) ** 2) == 0:
            apply(d, q)
    i += 1
for t in T:
    print(t + 1)
Problem p02632 (python)

Fixed submission:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')

class BinomialCoefficient(object):

    def __init__(self, N=510000, MOD=10**9+7):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

    def comb(self, n, r):
        if r < 0 or n < r or r < 0:
            return 0
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.MOD

K = I()
S = input()

bi = BinomialCoefficient(N=10 ** 6 * 2 + 1)
ans = 0
# i := Snのindex
for i in range(len(S) - 1, len(S) + K):
    tail = len(S) + K - i - 1
    lans = bi.comb(i, len(S) - 1)
    lans = lans * pow(25, K - tail, MOD) % MOD
    lans = lans * pow(26, tail, MOD) % MOD
    ans = (ans + lans) % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
class BinomialCoefficient(object):

    def __init__(self, N=510000, MOD=10**9+7):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

    def comb(self, n, r):
        if r < 0 or n < r or r < 0:
            return 0
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.MOD

K = I()
S = input()

bi = BinomialCoefficient(N=10 ** 6 + 1)
ans = 0
# i := Snのindex
for i in range(len(S) - 1, len(S) + K):
    tail = len(S) + K - i - 1
    lans = bi.comb(i, len(S) - 1)
    lans = lans * pow(25, K - tail, MOD) % MOD
    lans = lans * pow(26, tail, MOD) % MOD
    ans = (ans + lans) % MOD
print(ans)
Problem p02664 (python)

Fixed submission:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


T = input()

ans = list()
for i, c in enumerate(T):
    if c == '?':
        if len(ans) > 0 and ans[-1] == 'D' and i < len(T) - 1 and T[i + 1] in '?D':
            ans.append('P')
        else:
            ans.append('D')
    else:
        ans.append(c)
print(''.join(ans))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


T = input()

ans = list()
for i, c in enumerate(T):
    if c == '?':
        if i == len(T) - 1:
            ans.append('D')
        elif ans[-1] == 'D':
            ans.append('P')
        else:
            ans.append('D')
    else:
        ans.append(c)
print(''.join(ans))
Problem p02727 (python)

Fixed submission:
import sys
from bisect import bisect_right, bisect_left

def to_cumsum(arr, pad=True):
    """
    1次元配列を累積和の1次元配列に変換する
    pad: 先頭に0の項を作る場合はTrue
    """
    cumsum = 0
    padding = 1 if pad else 0
    new = [0] * (len(arr) + padding)
    for i, e in enumerate(arr):
        cumsum += e
        new[i + padding] = cumsum
    return new

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


X, Y, A, B, C = MI()
P = LMI()
Q = LMI()
R = LMI()

P.sort(reverse=True)
Q.sort(reverse=True)

R.extend(P[:X])
R.extend(Q[:Y])

R.sort(reverse=True)
print(sum(R[:X + Y]))

Buggy submission (verdict: Runtime Error):
import sys
from bisect import bisect_right, bisect_left

def to_cumsum(arr, pad=True):
    """
    1次元配列を累積和の1次元配列に変換する
    pad: 先頭に0の項を作る場合はTrue
    """
    cumsum = 0
    padding = 1 if pad else 0
    new = [0] * (len(arr) + padding)
    for i, e in enumerate(arr):
        cumsum += e
        new[i + padding] = cumsum
    return new

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


X, Y, A, B, C = MI()
P = LMI()
Q = LMI()
R = LMI()

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

Pcum = to_cumsum(P, pad=True)
Qcum = to_cumsum(Q, pad=True)
Rcum = to_cumsum(R, pad=True)


def bi(arr, v):
    l = 0
    r = len(arr) - 1
    while l + 1 < r:
        mid = (l + r) // 2
        if arr[mid] >= v:
            l = mid
        else:
            r = mid
    return r

ans = 0
for i in range(X + 1):
    a = Pcum[i]
    idx = bi(Q, R[X - i - 1])
    a += Qcum[idx]
    a += Rcum[min(idx, len(Rcum) - 1)]
    ans = max(ans, a)
print(ans)
Problem p02814 (python)

Fixed submission:
from fractions import gcd
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = list(map(lambda x: int(x) // 2, input().split()))

    X = A[0]
    for i in range(1, N):
        a, b = X, A[i]
        X = a * b // gcd(a, b)
        if X > M:
            print(0)
            exit(0)

    cnt = 0
    tmp = X
    while tmp % 2 == 0:
        tmp = tmp // 2
        cnt += 1
    for a in A:
        if a % (2 ** cnt) == 0 and a % (2 ** (cnt + 1)) != 0:
            continue
        else:
            print(0)
            exit(0)
    print((M // X + 1) // 2)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import numpy as np



N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = A // 2
v = np.lcm.reduce(A)

print((M // v + 1) // 2)
Problem p03044 (python)

Fixed submission:
import sys
sys.setrecursionlimit(200000)

N = int(input())

neighbors = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    neighbors[u].append((v, w))
    neighbors[v].append((u, w))

ans = [None for _ in range(N)]


def dfs(v, p, c):
    ans[v - 1] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans:
    print(e)

Buggy submission (verdict: Runtime Error):
N = int(input())

neighbors = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    neighbors[u].append((v, w))
    neighbors[v].append((u, w))

ans = [None for _ in range(N)]


def dfs(v, p, c):
    ans[v - 1] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans:
    print(e)

Buggy submission (verdict: Runtime Error):
N = int(input())

neighbors = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    neighbors[u].append((v, w))
    neighbors[v].append((u, w))

ans = [None for _ in range(N + 1)]


def dfs(v, p, c):
    ans[v] = c
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else 1 - c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans[1:]:
    print(e)

Buggy submission (verdict: Runtime Error):
N = int(input())

neighbors = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    neighbors[u].append((v, w))
    neighbors[v].append((u, w))

ans = [None for _ in range(N + 1)]
ans[1] = 0


def dfs(v, p, c):
    for next_v, distance in neighbors[v]:
        if next_v == p:
            continue
        next_c = c if distance % 2 == 0 else abs(c - 1)
        ans[next_v] = next_c
        dfs(next_v, v, next_c)


dfs(1, -1, 0)
for e in ans[1:]:
    print(e)

Buggy submission (verdict: Runtime Error):
N = int(input())

neighbors = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    neighbors[u].append((v, w))
    neighbors[v].append((u, w))

ans = [None for _ in range(N + 1)]
ans[1] = 0
seen = set()


def dfs(v, color):
    seen.add(v)
    for next_v, distance in neighbors[v]:
        if next_v in seen:
            continue
        next_color = color if distance % 2 == 0 else abs(color - 1)
        ans[next_v] = next_color
        dfs(next_v, next_color)


dfs(1, 0)
for e in ans[1:]:
    print(e)