Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

MOD = 1000000000+7

def two(a,n): #繰返し二乗法
    mul = a
    b = 1
    while n >= 1:
        if n & 1:
            b = b * mul % MOD
        n = n >> 1
        mul **= 2
        mul %= MOD
    return b

def inverse(a): #逆元を求める
    return two(a,MOD-2)

def comb(n,r): #コンビネーション
    ans = 1
    for i in range (r):
        ans *= (n-i) * inverse(i+1) % MOD
        ans %= MOD
    return ans

sum = two(2,n)
case = comb(n,a) + comb(n,b) + 1
ans = sum-case
if ans < 0 :
    ans += MOD

print(ans)

Fixed submission:
n,a,b = map(int,input().split())

mod = 10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

sum = pow(2,n,mod)
case = combination(n,a,mod) + combination(n,b,mod) + 1
ans = sum-case
while ans < 0 :
    ans += mod

print(ans)

Buggy python submission (verdict: Runtime Error):
1000000000 141421 173205

Fixed submission:
n,a,b = map(int,input().split())

mod = 10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

sum = pow(2,n,mod)
case = combination(n,a,mod) + combination(n,b,mod) + 1
ans = sum-case
while ans < 0 :
    ans += mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,a,b = map(int,input().split())

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def comb_fast(n,r):
    m = 10**9+7
    res = 1
    for i in range(1,n+1):
        res = res*i%m
    for i in range(1,r+1):
        res = res*mod_inv(i,m)%m
    for i in range(1,n-r+1):
        res = res*mod_inv(i,m)%m
    return res

def two_to(n):
    bi = format(n,"b")
    bi_list = list(bi)
    bi_list.reverse()
    s = 1
    for i in range (0,len(bi_list)):
        if bi_list[i] == "1":
            s *= 2**(2**i)
            s = s%1000000007
    return s

sum = two_to(n)
sub = comb_fast(n,a)+comb_fast(n,b)
ans = sum - sub -1

print(ans)

Fixed submission:
n,a,b = map(int,input().split())

mod = 10**9+7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

sum = pow(2,n,mod)
case = combination(n,a,mod) + combination(n,b,mod) + 1
ans = sum-case
while ans < 0 :
    ans += mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int, input().split()))
s=0
for i in range(0,N):
    for j in range(i+1,N):
        if A[i]==A[j]:
            s=s+1
if s==0:
    print("YES")
else:
    print("NO")

Fixed submission:
N=int(input())
A=list(map(int, input().split()))

if len(A)==len(set(A)):
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
[N,K]=list(map(int, input().split()))
p=list(map(int, input().split()))

def ex(p,n):
    return (p[n]+1)/2

def  sum(p,n):
    s=0
    for i in range (0,n+1):
        s=s+ex(p,i)
    return s

list=[]
for i in range (0,N):
    list.append(sum(p,i))

max=list[K-1]
for i in range (0,N-K):
   if list[i+K]-list[i] >= max:
        max=list[i+K]-list[i]
        
print(max)

Fixed submission:
[N,K]=list(map(int, input().split()))
p=list(map(int, input().split()))

def ex(p,n):
    return (p[n]+1)/2


list=[]
s=0
for i in range (0,N):
    s=s+ex(p,i)
    list.append(s)

max=list[K-1]
for i in range (0,N-K):
   if list[i+K]-list[i] >= max:
        max=list[i+K]-list[i]
        
print(max)

Buggy python submission (verdict: Time Limit Exceeded):
[N,K]=list(map(int, input().split()))
p=list(map(int, input().split()))

def ex(p,n):
    return (p[n-1]+1)/2

def sum(p,n,K):
    s=0
    for i in range (0,K):
        s=s+ex(p,n+i)
    return s

max=sum(p,1,K)
for i in range (1,N-K+1):
   if sum(p,i+1,K)>=max:
        max=sum(p,i+1,K)
        
print(max)

Fixed submission:
[N,K]=list(map(int, input().split()))
p=list(map(int, input().split()))

def ex(p,n):
    return (p[n]+1)/2


list=[]
s=0
for i in range (0,N):
    s=s+ex(p,i)
    list.append(s)

max=list[K-1]
for i in range (0,N-K):
   if list[i+K]-list[i] >= max:
        max=list[i+K]-list[i]
        
print(max)
Buggy python submission (verdict: Runtime Error):
[N]=list(map(int, input().split()))
A=list(map(int, input().split()))
c=0
for i in range (0,N):
    B=sorted(A[0:i+1],reverse=True)
    if B[i] == A[i]:
        c=c+1
print(c)

Fixed submission:
[M,N]=list(map(int, input().split()))
if M==N:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
[N]=list(map(int, input().split()))
A=list(map(int, input().split()))
c=0
for i in range (0,N):
    B=sorted(A[0:i+1],reverse=True)
    if B[i] == A[i]:
        c=c+1
print(c)

Fixed submission:
[N]=list(map(int, input().split()))
A=list(map(int, input().split()))
c=0
min=A[0]
for i in range (0,N):
    if A[i]<=min:
        min=A[i]
        c=c+1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

X = lcm(A)
ans = 0
for i in range(N):
    ans += X//A[i]
    ans %= MOD
print(ans)

Fixed submission:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

X = lcm(A)
ans = 0
for i in range(N):
    ans += X//A[i]
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
[A,B,K]=list(map(int, input().split()))
for i in range (0,K):
    if A >= 1:
        A=A-1
    elif B >= 1:
        B=B-1
print(str(A)+" "+str(B))

Fixed submission:
[A,B,K]=list(map(int, input().split()))
if A<=K:
    a=0
    if B<=K-A:
        B=0
    else:
        B=A+B-K
else:
    a=A-K
print(str(a)+" "+str(B))
Buggy python submission (verdict: Runtime Error):
import math

a,b= map(int,input().split())

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))

Fixed submission:
import fractions

a,b= map(int,input().split())

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

print(lcm(a, b))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
S.append("a")
n = list(map(str,range(0,10)))
ans = 0
for i in n:
    for j in n:
        for k in n:
            num = i+j+k
            now = 0

            for l in range(N+1):
                if now == 3:
                    ans += 1
                    break
                if num[now] == S[l]:
                    now += 1
print(ans)

Fixed submission:
N = int(input())
S = list(input())
S.append("a")
n = list(map(str,range(0,10)))
ans = 0
for i in n:
    for j in n:
        for k in n:
            num = i+j+k
            now = 0

            for l in range(N+1):
                if now == 3:
                    ans += 1
                    break
                if num[now] == S[l]:
                    now += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq

N = int(input())

color = [[] for _ in range(N)]
ans = [None]*(N-1)


for i in range(N):
    heapq.heapify(color[i])

for i in range(N-1):
    a,b = map(int,input().split())
    
    if i == 0:
        color[a-1].append(1)
        color[b-1].append(1)
        ans[i] = 1

    else:
        if color[a-1]:
            if color[a-1][0] != 1:
                mim = heapq.heappop(color[a-1])
                heapq.heappush(color[a-1],mim)
                heapq.heappush(color[a-1],mim-1)
                heapq.heappush(color[b-1],mim-1)
                ans[i] = mim-1
            else:
                nax = color[a-1][-1]
                heapq.heappush(color[a-1],nax+1)
                heapq.heappush(color[b-1],nax+1)
                ans[i] = nax+1
        else:
            if color[b-1][0]!= 1:
                mim = heapq.heappop(color[b-1])
                heapq.heappush(color[b-1],mim)
                heapq.heappush(color[b-1],mim-1)
                heapq.heappush(color[a-1],mim-1)
                ans[i] = mim-1
            else:
                nax = color[b-1][-1]
                heapq.heappush(color[b-1],nax+1)
                heapq.heappush(color[a-1],nax+1)
                ans[i] = nax+1

print(max(ans))
for i in range(N-1):
    print(ans[i])

Fixed submission:
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
color = [[] for _ in range(N)]
mi = [[] for _ in range(N)]
MA = [[] for _ in range(N)]
edge = {}
ans = [0]*(N-1)
M = 0

for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    ans[i] = (a,b)

stack = deque([0])
not_visit = [True]*N
not_visit[0] = False
while stack:
    now = stack.popleft()
    for i in g[now]:
        if not_visit[i]:
            stack.append(i)
            if not mi[now]:
                mi[now] = 1
                MA[now] = 1
                mi[i] = 1
                MA[i] = 1
                M = 1
                color[now].append(mi[now])
                color[i].append(mi[now])
                edge[(now+1,i+1)] = mi[now]
                edge[(i+1,now+1)] = mi[now]
            else:
                if mi[now] != 1:
                    mi[now] -= 1
                    color[now].append(mi[now])
                    color[i].append(mi[now])
                    edge[(now+1,i+1)] = mi[now]
                    edge[(i+1,now+1)] = mi[now]
                    if mi[i]:
                        mi[i] = min(mi[i],mi[now])
                    else:
                        mi[i] = mi[now]
                        MA[i] = mi[now]
                else:
                    MA[now] += 1
                    color[now].append(MA[now])
                    color[i].append(MA[now])
                    edge[(now+1,i+1)] = MA[now]
                    edge[(i+1,now+1)] = MA[now]
                    M = max(M,MA[now])
                    if MA[i]:
                        MA[i] = max(MA[i],MA[now])
                    else:
                        MA[i] = MA[now]
                        mi[i] = MA[now]

            not_visit[i] = False

print(M)
for i in range(N-1):
    print(edge[ans[i]])
Buggy python submission (verdict: Time Limit Exceeded):
X,Y=map(int,input().split())

def stair(n):
    m=1
    for i in range (2,n+1):
        m=m*i
    return m

def comb(n,r):
    return stair(n)//(stair(r)*stair(n-r))

if (X+Y)%3==0 and (X+Y)//3>=abs(X-Y):
    ans=comb((X+Y)//3,( (X+Y)//3 - abs(X-Y) )//2)
    print(ans%1000000009)
else:
    print(0)

Fixed submission:
X,Y=map(int,input().split())

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

if (X+Y)%3==0 and (X+Y)//3>=abs(X-Y):
    ans=combination((X+Y)//3,( (X+Y)//3 - abs(X-Y) )//2)
    print(ans%1000000007)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int,input().split()))
L.sort()

c=0
for i in range (N-2):
    for j in range (i+1,N-1):
        for k in range (j+1,N):
            if L[i]+L[j] > L[k]: #and L[j]+L[k] > L[i] and L[k]+L[i] > L[j]:
                c += 1
            else:
                break

print(c)

Fixed submission:
N = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        zum = L[i]+L[j]
        start = j+1
        goal = N-1
        now = (start + goal)//2

        if zum > L[goal]:
            c += goal - j
        elif zum <= L[start]:
            c += 0
        else:
            while not L[now] < zum <= L[now+1]:
                now = (start + goal)//2
                if zum > L[now]:
                    start = now
                else:
                    goal = now
            c += now - j

print(c)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int,input().split()))

c=0
for i in range (N-2):
    for j in range (i+1,N-1):
        for k in range (j+1,N):
            if L[i]+L[j] > L[k] and L[j]+L[k] > L[i] and L[k]+L[i] > L[j]:
                c += 1

print(c)

Fixed submission:
N = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        zum = L[i]+L[j]
        start = j+1
        goal = N-1
        now = (start + goal)//2

        if zum > L[goal]:
            c += goal - j
        elif zum <= L[start]:
            c += 0
        else:
            while not L[now] < zum <= L[now+1]:
                now = (start + goal)//2
                if zum > L[now]:
                    start = now
                else:
                    goal = now
            c += now - j

print(c)
Buggy python submission (verdict: Time Limit Exceeded):
N, K, Q = map(int,input().split())
A = [0]*Q
survive = [0]*N

for i in range (Q):
    A[i] = input()

for i in range (N):
    c=A.count(str(i+1))
    if Q-c >= K:
        survive[i] = "No"
    else:
        survive[i] = "Yes"

ans = '\n'.join(survive)
print(ans)

Fixed submission:
N, K, Q = map(int,input().split())
A = [0]*Q
survive = [0]*N

for i in range (Q):
    A[i] = int(input())

result={}
for i in range (0,len(A)):
    item = A[i]
    if item in result:
        result[item] = result[item]+1
    else:
        result[item] = 1

for i in range (1,N+1):
    item = i
    if item not in result:
        result[item] = 0

result_sort = sorted(result.items())

for i in range (N):
    if Q - result_sort[i][1] >= K:
        print("No")
    else:
        print("Yes")
Buggy python submission (verdict: Runtime Error):
N = int(input())
H = list(map(int,input().split()))
gap = [0]*(N-1)
M = []

for i in range (N-1):
    gap[i] = H[i]-H[i+1]

c = 0
for i in range (N-1):
    if gap[i] >= 0:
        c += 1
        if i == N-2:
            M.append(c)
    else:
        M.append(c)
        c = 0

if N == 1:
    M = 0
    
print(max(M))

Fixed submission:
N = int(input())
H = list(map(int,input().split()))
gap = [0]*(N-1)
M = []

for i in range (N-1):
    gap[i] = H[i]-H[i+1]

c = 0
for i in range (N-1):
    if gap[i] >= 0:
        c += 1
        if i == N-2:
            M.append(c)
    else:
        M.append(c)
        c = 0

if N == 1:
    print(0)
else:
    print(max(M))

Buggy python submission (verdict: Runtime Error):
N = int(input())
H = list(map(int,input().split()))
gap = [0]*(N-1)
M = []

for i in range (N-1):
    gap[i] = H[i]-H[i+1]

c = 0
for i in range (N-1):
    if gap[i] >= 0:
        c += 1
        if i == N-2:
            M.append(c)
    else:
        M.append(c)
        c = 0

print(max(M))

Fixed submission:
N = int(input())
H = list(map(int,input().split()))
gap = [0]*(N-1)
M = []

for i in range (N-1):
    gap[i] = H[i]-H[i+1]

c = 0
for i in range (N-1):
    if gap[i] >= 0:
        c += 1
        if i == N-2:
            M.append(c)
    else:
        M.append(c)
        c = 0

if N == 1:
    print(0)
else:
    print(max(M))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

#print(graph)
v = [0]*N
for i in range(Q):
    p,x = map(int,input().split())
    v[p-1] += x

notv = [True]*N
notv[0] = False
stack = [0]

while stack:
    now = stack.pop(0)
    for i in graph[now]:
        if notv[i]:
            notv[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)

Fixed submission:
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
graph = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

#print(graph)
v = [0]*N
for i in range(Q):
    p,x = map(int,input().split())
    v[p-1] += x

notv = [True]*N
notv[0] = False
stack = [0]

while stack:
    now = stack.pop()
    for i in graph[now]:
        if notv[i]:
            notv[i] = False
            stack.append(i)
            v[i] += v[now]

print(*v)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N,M = map(int,(input().split()))
A = [0]*N
B = [0]*N
mission = [[] for _ in range(M+1)]
work = 0

for i in range(N):
    if i <= M:
        heapq.heapify(mission[i])
    A[i],B[i] = map(int,(input().split()))
    if A[i] <= M:
        mission[A[i]].append(-B[i])

for day in range(1,M+1):
    mission[day].extend(mission[day-1])
    if mission[day]:
        heapq.heapify(mission[day])
        work += heapq.heappop(mission[day])

print(-work)

Fixed submission:
import heapq

N,M = map(int,(input().split()))
A = [0]*N
B = [0]*N
mission = [[] for _ in range(M+1)]
work = 0

for i in range(N):
    if i <= M:
        heapq.heapify(mission[i])
    A[i],B[i] = map(int,(input().split()))
    if A[i] <= M:
        mission[A[i]].append(-B[i])

for day in range(1,M+1):
    for i in range(len(mission[day])):
        heapq.heappush(mission[0],mission[day][i])
    if mission[0]:
        work += heapq.heappop(mission[0])

print(-work)
Buggy python submission (verdict: Runtime Error):
L,R = map(int,input().split())

if R - L >= 2018:
    print(0)
else:
    m = 2020
    for i in range(L,R):
        for j in range(i+1,R+1):
            mod = i * j % 2019
            if mod <= m:
                m = mod

print(m)

Fixed submission:
L,R = map(int,input().split())

if R - L >= 2018:
    print(0)
else:
    min = 2020
    for i in range(L,R):
        for j in range(i+1,R+1):
            mod = i * j % 2019
            if mod <= min:
                min = mod
    print(min)
Buggy python submission (verdict: Runtime Error):
p,q,r = map(int,input().split())
print(min(p+q,q+r,r+s))

Fixed submission:
p,q,r = map(int,input().split())
print(min(p+q,q+r,r+p))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[]
for i in range(m):
    A=int(input())
    a.append(A)
b=[0,1]
ans=1
for i in range(1,n+1):
    if i in a:
        b.append(0)
    else:
        b.append(b[i]+b[i-1])
    b[i]=b[i]%1000000007
print(b[len(b)-1]%1000000007)

Fixed submission:
N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

step = [0]*(N+1)
step[0] = 1

for i in range(M):
    step[a[i]] = -1

if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if step[i] == -1:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

step = [0]*(N+1)
step[0] = 1
if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if i in a:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)

Fixed submission:
N,M = map(int,input().split())
a = [0]*M
for i in range(M):
    a[i] = int(input())

step = [0]*(N+1)
step[0] = 1

for i in range(M):
    step[a[i]] = -1

if 1 in a:
    step[1] = 0
else:
    step[1] = 1

for i in range(2,N+1):
    if step[i] == -1:
        step[i] = 0
    else:
        step[i] = (step[i-1] + step[i-2])%(10**9+7)

print(step[N])

#再起関数供養
def count_step(a,n):
    if n == 0:
        return 1
    if n == 1 and 1 not in a:
        return 1
    if n in a:
        return 0
    return (count_step(a,n-1)+count_step(a,n-2))%(10**9+7)
Buggy python submission (verdict: Runtime Error):
import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(M)]

B.sort(key=lambda B:B[1],reverse=True)
heapq.heapify(A)

for i in range(M):
    for j in range(B[i][0]):
        c += 1
        if c > N:
            break
        if A[0] < B[i][1]:
            heapq.heappop(A)
            heapq.heappush(A,B[i][1])
            print(A)
        else:
            break
    else:
        continue
    break
    
print(sum(A))

Fixed submission:
import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(M)]

B.sort(key=lambda B:B[1],reverse=True)
heapq.heapify(A)

c = 0
for i in range(M):
    for j in range(B[i][0]):
        c += 1
        if c > N:
            break
        if A[0] < B[i][1]:
            heapq.heappop(A)
            heapq.heappush(A,B[i][1])
            #print(A)
        else:
            break
    else:
        continue
    break
    
print(sum(A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
g = [[[]for i in range(2)] for j in range(N)]

for i in range(N-1):
    u,v,d = map(int,input().split())
    if d%2 == 0:
        g[u-1][0].append(v-1)
        g[v-1][0].append(u-1)
    else:
        g[u-1][1].append(v-1)
        g[v-1][1].append(u-1)

ans = [-1]*N
ans[0] = 0

stack = [0]
not_visit = [True for i in range(N)]
not_visit[0] = False

while stack:
    now = stack.pop()
    for h in range(2):
        for i in range(len(g[now][h])):
            if not_visit[g[now][h][i]]: #距離が偶数ならば
                not_visit[g[now][0][i]] = False
                ans[g[now][0][i]] = ans[now]
                stack.append(g[now][0][i])
        for i in range(len(g[now][h])):
            if not_visit[g[now][h][i]]: #距離が奇数ならば
                not_visit[g[now][1][i]] = False
                ans[g[now][1][i]] = (ans[now] + 1)%2
                stack.append(g[now][1][i])

for i in range(N):
    print(ans[i])

Fixed submission:
N = int(input())
g = [[[]for i in range(2)] for j in range(N)]

for i in range(N-1):
    u,v,d = map(int,input().split())
    if d%2 == 0:
        g[u-1][0].append(v-1)
        g[v-1][0].append(u-1)
    else:
        g[u-1][1].append(v-1)
        g[v-1][1].append(u-1)

ans = [-1]*N
ans[0] = 0

stack = [0]
not_visit = [True for i in range(N)]
not_visit[0] = False

while stack:
    now = stack.pop()
    for h in range(2):
        if h == 0: #距離が偶数ならば
            for i in range(len(g[now][h])):
                if not_visit[g[now][h][i]]:
                    not_visit[g[now][h][i]] = False
                    ans[g[now][h][i]] = ans[now]
                    stack.append(g[now][h][i])
        if h == 1: #距離が奇数ならば
            for i in range(len(g[now][h])):
                if not_visit[g[now][h][i]]:
                    not_visit[g[now][h][i]] = False
                    ans[g[now][h][i]] = (ans[now] + 1)%2
                    stack.append(g[now][h][i])

for i in range(N):
    print(ans[i])