Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
def comb_mod(n,r,mod):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans

A, B, C, D = map(int, input().split())

ans = comb_mod(C+D+2,C+1,mod)-comb_mod(B+C+1,B,mod)-comb_mod(A+D+1,A,mod)+comb_mod(A+B,A,mod)
print(ans%mod)

Fixed submission:
mod = 10**9+7
def comb_mod(n,r,mod,invs):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    ans *= invs[r]
    ans %= mod
    return ans

A, B, C, D = map(int, input().split())

invs = [1]*(C+2)
for i in range(1,C+2):
    invs[i] = invs[i-1]*pow(i,mod-2,mod)
    invs[i] %= mod
ans = comb_mod(C+D+2,C+1,mod,invs)-comb_mod(B+C+1,B,mod,invs)-comb_mod(A+D+1,A,mod,invs)+comb_mod(A+B,A,mod,invs)
print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    H, N = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    dp = [float('inf')]*(H+10**4)
    dp[0] = 0
    for h in range(1,H+10**4):
        for i in range(N):
            if A[i][0]<=h:
                dp[h] = min(dp[h],dp[h-A[i][0]]+A[i][1])
    ans = min(dp[H:])
    return ans
print(solve())

Fixed submission:
#動的計画法
import numpy as np
H, N = map(int, input().split())

A=np.empty(N,dtype=int)
B=np.empty(N,dtype=int)
for i in range(N):
    A[i],B[i]=map(int,list(input().split(" ")))

DP=np.empty(H+1,dtype=int)

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  t = hp-A
  t[t<0] = 0
  min_power = min(DP[t]+B)
  return magic+min_power

#DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
#動的計画法
H, N = map(int, input().split())

A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, input().split())

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  min_power = min([DP[max(hp-A[i],0)]+B[i] for i in range(N)])
  return magic+min_power

DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')

Fixed submission:
#動的計画法
import numpy as np
H, N = map(int, input().split())

A=np.empty(N,dtype=int)
B=np.empty(N,dtype=int)
for i in range(N):
    A[i],B[i]=map(int,list(input().split(" ")))

DP=np.empty(H+1,dtype=int)

def battle(hp,magic=0):
  #print(hp,magic)
  if hp==0:
    return magic
  t = hp-A
  t[t<0] = 0
  min_power = min(DP[t]+B)
  return magic+min_power

#DP = [0]*(H+1)
for i in range(H+1):
  DP[i] = battle(i)
  #print(DP[i])
ans = DP[H]
print(ans)

#print(*ans, sep='\n')
Buggy python submission (verdict: Runtime Error):
from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())from bisect import *
def solve():
  ans = 0
  N, D, A = map(int, input().split())
  B = [list(map(int, input().split())) for _ in range(N)]
  B.sort()
  lasts = [0]*(N+1)
  now = 0
  for i,((x,h),l) in enumerate(zip(B,lasts)):
    now -= l
    atack = max(0,-(-(h-now)//A))
    ans += atack
    damage = atack*A
    now += damage
    last = x+2*D
    ind = bisect_right(B,[last+1,0])
    lasts[ind] += damage
  return ans
print(solve())

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

Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))

Monster.sort(key=lambda x:x[0])

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

from collections import deque

d = deque()
damage = 0
ans = 0
for i in range(N):
    while len(d)>0:
        a = d.popleft()
        if a[0]==i:
            damage -= a[1]
        else:
            d.appendleft(a)
            break
    Monster[i][1] -= damage
    count = -(-max(Monster[i][1],0)//A)
    ans += count
    right = Monster[i][0]+2*D
    ind = bisect(Monster,[right,10**9+1])
    damage += A*count
    d.append([ind,A*count])
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
if N%2 == 1:
  print(0)
  exit()
five = N//10
for i in range(int(math.log(N//10,5))):
  five += N//(10*5**(i+1))
print(five)
124999999999999995

Fixed submission:
import math

N = int(input())
if N%2 == 1 or N<10:
  print(0)
  exit()
five = N//10
for i in range(int(math.log(N//10,5))):
  five += N//(10*5**(i+1))
print(five)
Buggy python submission (verdict: Runtime Error):
import math
import itertools
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
color = [0]*3
ans = 1
for i in range(N):
  ind = color.index(A[i])
  ans *= len([c for c in color if c == A[i]])
  ans %= mod
  color[ind] += 1

#ans = rec(color,0)
print(ans)

Fixed submission:
import math
import itertools
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
color = [0]*3
ans = 1
for i in range(N):
  if A[i] not in color:
    ans = 0
    break
  ind = color.index(A[i])
  ans *= len([c for c in color if c == A[i]])
  ans %= mod
  color[ind] += 1

#ans = rec(color,0)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

#@njit((i8,i8,i8[:]), cache=True)
def main(N,T,A):
  dp = np.zeros(T+1, np.int64)
  for i in range(N):
    for t in range(T-1,-1,-1):
      u = min(T,t+A[i,0])
      dp[u] = max(dp[u],dp[t]+A[i,1])
  ans = dp[-1]
  return ans

N, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
A = np.array(sorted(A))
print(main(N,T,A))

Fixed submission:
#dp[n][t]=max(dp[n-1][t],dp[n-1][t-A[n]]+B[n])
#dp[0][t]=0, dp[n][0]=0,0<=t<=T+max(B)-1, 0<=n<=N
def solve():
    N, T = map(int, input().split())
    X = [list(map(int, input().split())) for _ in range(N)]
    X.sort()
    dp = [[0]*(T+3000) for _ in range(N+1)]
    for n in range(1,N+1):
        for t in range(1,T+X[n-1][0]):
            dp[n][t]=dp[n-1][t]
            if t>=X[n-1][0]:
                dp[n][t]=max(dp[n][t],dp[n-1][t-X[n-1][0]]+X[n-1][1])
    ans = max(dp[N])
    return ans
print(solve())

Buggy python submission (verdict: Runtime Error):
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:,:]), cache=True)
def main(N,T,A):
  dp = np.zeros(T+1,np.int64)
  for a,b in A:
    for t in range(T-1,-1,-1):
      u = min(T,t+a)
      dp[u] = max(dp[u],dp[t]+b)
  ans = dp[-1]
  return ans

N, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
A = np.array(sorted(A))
print(main(N,T,A))

Fixed submission:
#dp[n][t]=max(dp[n-1][t],dp[n-1][t-A[n]]+B[n])
#dp[0][t]=0, dp[n][0]=0,0<=t<=T+max(B)-1, 0<=n<=N
def solve():
    N, T = map(int, input().split())
    X = [list(map(int, input().split())) for _ in range(N)]
    X.sort()
    dp = [[0]*(T+3000) for _ in range(N+1)]
    for n in range(1,N+1):
        for t in range(1,T+X[n-1][0]):
            dp[n][t]=dp[n-1][t]
            if t>=X[n-1][0]:
                dp[n][t]=max(dp[n][t],dp[n-1][t-X[n-1][0]]+X[n-1][1])
    ans = max(dp[N])
    return ans
print(solve())
Buggy python submission (verdict: Runtime Error):
N = int(input())
kuku = []
for i in range(1,10):
  for j in range(1,10):
    kuku.append(i*j)
if N in kuku:
  print('Yes')
else:
  print('No')

Fixed submission:
import math
A, B = map(int, input().split())
if A>9 or B>9:
  print(-1)
  exit()
print(A*B)
Buggy python submission (verdict: Runtime Error):
a, b, x = map(int, input().split())
from math import atan,pi
if x<= a*a*b/2:
    print(90-atan((x*2/b/a)/b)*180/pi)
    exit()
else:
    print(90-atan(a/((a*a*b-x)*2/a/a))*180/pi)
    

Fixed submission:
import math
a, b, x = map(int, input().split())
if x == a*a*b:
  print(0)
  exit()
if x/a/a*2>=b:
  h = x/a/a*2-b
  rad = math.atan(a/(b-h))
else:
  rad = math.atan(x/a*2/b/b)
print(90-math.degrees(rad))

Buggy python submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())
if x/a/a*2>=b:
  h = x/a/a*2-b
  rad = math.atan(a/(b-h))
else:
  rad = math.atan(x/a*2/b/b)
print(90-math.degrees(rad))

Fixed submission:
import math
a, b, x = map(int, input().split())
if x == a*a*b:
  print(0)
  exit()
if x/a/a*2>=b:
  h = x/a/a*2-b
  rad = math.atan(a/(b-h))
else:
  rad = math.atan(x/a*2/b/b)
print(90-math.degrees(rad))
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())

cnt = 0
serial = 1
for i in range(len(S)):
  if S[i] == S[(i+1)%len(S)]:
    serial += 1
  else:
    cnt += int(serial/2)
    serial = 1
  #print(serial)
cnt += int(serial/2)
      
#print(cnt)
if S[0]==S[-1] and S[-1]!=S[-2]:
  ans = cnt*K-1
  
else:
  ans = cnt*K

print(ans)

Fixed submission:
S = input()
K = int(input())

if len(set(S))==1:
  ans = int(len(S)*K/2)
elif K == 1:
  ans = 0
  serial = 1
  #print(serial)
  for i in range(len(S)-1):
    if S[i] == S[i+1]:
      serial += 1
    else:
      ans += int(serial/2)
      serial = 1
  ans += int(serial/2)
else:
  #first
  first=0
  serial = 1
  for i in range(len(S)-1):
    if S[i] == S[i+1]:
      serial += 1
    else:
      first += int(serial/2)
      serial = 1
  initial = 1
  for i in range(len(S)-1,1,-1):
    if S[i]==S[i-1]:
      initial += 1
    else:
      break
  cnt = 0
  serial = initial
  #print(serial)
  for i in range(len(S)):
    if S[i] == S[i-1]:
      serial += 1
    else:
      cnt += int(serial/2)
      serial = 1
    #print(cnt)
  #last
      
  #print(cnt)
  last = 0
  serial = initial
  for i in range(len(S)):
    if S[i] == S[i-1]:
      serial += 1
    else:
      last += int(serial/2)
      serial = 1
  last += int(serial/2)
  #print(first,cnt,last)
  ans = first+(K-2)*cnt+last

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

import bisect

for i in range(M):
  M = max(A)
  A.remove(M)
  x = M//2
  A.append(x)
print(sum(A))

  

Fixed submission:
N, M = map(int, input().split())
A = list(map(lambda x:(-1)*int(x), input().split()))
import heapq  # heapqライブラリのimport

heapq.heapify(A)  # リストを優先度付きキューへ

# 最小値の取り出し

for i in range(M):
  heapq.heappush(A, ((-1)*heapq.heappop(A))//2*(-1))

print(sum(A)*(-1))

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

import bisect

for i in range(M):
  x = A[-1]//2
  insert_index = bisect.bisect_left(A[:-1],x)
  A = A[:-1] 
  A.insert(insert_index,x)
print(sum(A))

Fixed submission:
N, M = map(int, input().split())
A = list(map(lambda x:(-1)*int(x), input().split()))
import heapq  # heapqライブラリのimport

heapq.heapify(A)  # リストを優先度付きキューへ

# 最小値の取り出し

for i in range(M):
  heapq.heappush(A, ((-1)*heapq.heappop(A))//2*(-1))

print(sum(A)*(-1))
Buggy python submission (verdict: Runtime Error):
N, Q = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

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

from collections import deque

visited = [False]*N
d = deque([0])
while len(d)>0:
    v = d.popleft()
    visited[v]= True
    for u in edge[v]:
        if visited[u]==False:
            ans[u] += ans[v]
            visited[u]=True
            d.append(u)

print(*ans, sep=' ')

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()
dic = {}
for i,s in enumerate(S):
  if s not in dic:
    dic[s] = [i]
  else:
    dic[s].append(i)
#print(dic)
ind = -1
loop = 0
for t in T:
  if t not in dic:
    ans = -1
    break
  if dic[t][-1]<=ind:
    loop += 1
    ind = dic[t][0]
  else:
    for i in dic[t]:
      if i > ind:
        ind = i
        break
  #print(ind)
#print(loop,ind)
else:
  ans = len(S)*loop+ind+1
          
print(ans)   

#print(*ans[1:], sep='\n')


Fixed submission:
S = input()
T = input()
dic = {}
for i,s in enumerate(S):
  if s not in dic:
    dic[s] = [i]
  else:
    dic[s].append(i)
#print(dic)
ind = -1
loop = 0
import bisect
for t in T:
  if t not in dic:
    ans = -1
    break
  if dic[t][-1]<=ind:
    loop += 1
    ind = dic[t][0]
  else:
    i = bisect.bisect_right(dic[t],ind)
    ind = dic[t][i]
  #print(ind)
#print(loop,ind)
else:
  ans = len(S)*loop+ind+1
          
print(ans)   

#print(*ans[1:], sep='\n')
Buggy python submission (verdict: Runtime Error):
def solve():
    ans = 0
    N, M, P = map(int, input().split())
    edge = []
    for i in range(M):
        a,b,c = map(int, input().split())
        edge.append([P-c,a-1,b-1])
    d = [10**10]*N
    d[0]=0
    n = 0
    while True:
        n += 1
        update = False
        if n==N:
            updateN = False
        for i in range(M):
            w,u,v = edge[i]
            if d[u]<10**10 and d[v]>d[u]+w:
                d[v] = d[u]+w
                update = True
                if n>=N and v==N-1:
                    updateN = True
        if not update:
            break
        if n==N+M:
            if updateN:
                return -1
            break
    return max(0,-d[-1])
print(solve())

Fixed submission:
def solve():
    ans = 0
    A, B = map(int, input().split())
    ans = max([A+B,A-B,A*B])
    return ans
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from collections import deque
def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_left(lis,A[i])
        if ind == 0:
            lis.insert(0,A[i])
        else:
            lis[ind-1] = A[i]
    ans = len(lis)
    return ans
print(solve(N,A))

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort

def solve(N,A):
    ans = 0
    lis = []
    for i in range(N):
        ind = bisect_right(lis,-A[i])
        if ind == len(lis):
            lis.append(-A[i])
        else:
            lis[ind] = -A[i]
    ans = len(lis)
    return ans
print(solve(N,A))
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
def comb_mod(n,r,mod):
    ans = 1
    for i in range(r):
        ans *= n-i
        ans %= mod
    for i in range(1,r+1):
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans
def solve():
    N, K = map(int, input().split())
    ans = []
    for i in range(1,K+1):
        ans.append(comb_mod(K-1,i-1,mod)*comb_mod(N-K+1,i,mod)%mod)
    return ans
print(*solve(),sep='\n')

Fixed submission:
def solve():
    mod = 10**9+7
    N, K = map(int, input().split())
    ans = []
    combs1 = [1]*K
    combs2 = [1]*(K+1)
    for i in range(1,K):
        combs1[i] = combs1[i-1]*(K-i)*pow(i,mod-2,mod)%mod
    for i in range(1,K+1):
        combs2[i] = combs2[i-1]*(N-K+2-i)*pow(i,mod-2,mod)%mod
    for i in range(1,K+1):
        ans.append(combs1[i-1]*combs2[i]%mod)
    return ans
print(*solve(),sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
def solve():
  ans = 0
  mod = 10**9+7
  s = defaultdict(lambda: -1)
  t = defaultdict(lambda: -1)
  N, M = map(int, input().split())
  S = list(map(int, input().split()))
  T = list(map(int, input().split()))
  for i in range(N):
    s[S[i]] = i
  for j in range(M):
    t[T[j]] = j
  dp = [[0]*(M+1) for _ in range(N+1)]
  for j in range(M+1):
    dp[0][j] = 1
  for i in range(1,N+1):
    dp[i][0] = 1
  for i in range(1,N+1):
    for j in range(1,M+1):
      if S[i-1]==T[j-1]:
        dp[i][j] += dp[i-1][j]+dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
  ans = dp[-1][-1]%mod
  return ans
print(solve())

Fixed submission:
from collections import defaultdict
def solve():
  ans = 0
  mod = 10**9+7
  s = defaultdict(lambda: -1)
  t = defaultdict(lambda: -1)
  N, M = map(int, input().split())
  S = list(map(int, input().split()))
  T = list(map(int, input().split()))
  dp = [[0]*(M+1) for _ in range(N+1)]
  for j in range(M+1):
    dp[0][j] = 1
  for i in range(1,N+1):
    dp[i][0] = 1
  for i in range(1,N+1):
    for j in range(1,M+1):
      if S[i-1]==T[j-1]:
        dp[i][j] += dp[i-1][j]+dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
      dp[i][j]%= mod
  ans = dp[-1][-1]%mod
  return ans
print(solve())
Buggy python submission (verdict: Runtime Error):
#import numpy as np
H, W = map(int, input().split())
S = [0]*H
counth = [[0]*W for _ in range(H)]  
countw = [[0]*W for _ in range(H)]

for i in range(H):
  S[i] = input()
  
for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      if counth[i][j]==0:
        b=False
        for k,s in enumerate(S[i][j:]):
          if s=='#':
            b = True
            break
        if b==False:
          k+=1
        #print(S[i][j:],l)
        counth[i][j:j+k]=[k]*k
      if countw[i][j]==0:
        b=False
        for k in range(i,H):
          if S[k][j]=='#':
            b=True
            break
        if b==False:
          k+=1
        #print(S[i:][j],m)
        for l in range(i,k):
          #print(i,j,l)
          countw[l][j]=k
      #print(i,j,count)
#print(count)
maxim = 0
for i in range(H):
  for j in range(W):
    maxim = int(max(maxim,counth[i][j]+countw[i][j]-1))
print(maxim)

Fixed submission:
A, B, C = map(int, input().split())
print(A+B+C-max(A,B,C))
Buggy python submission (verdict: Runtime Error):
N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      #print(v)
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
visited[1]=True
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

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

N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      #print(v)
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
visited[1]=True
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

Buggy python submission (verdict: Runtime Error):
N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

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

N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      #print(v)
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
visited[1]=True
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

Buggy python submission (verdict: Runtime Error):
N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
dfs(1)
ans = color[1:]
print(*ans,sep='\n')

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

N = int(input())
edge = [[] for _ in range(N+1)]
for i in range(N-1):
  u,v,w = map(int, input().split())
  edge[u].append([v,w%2])
  edge[v].append([u,w%2])
color = [0]*(N+1)
visited = [False]*(N+1)
def dfs(u):
  for v,w in edge[u]:
    if visited[v]==False:
      #print(v)
      visited[v]=True
      color[v]=color[u]^w
      dfs(v)
  return 0
visited[1]=True
dfs(1)
ans = color[1:]
print(*ans,sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(v):
  if len(edge[v])==0:
    return 0
  for u in edge[v]:
    if visited[u]==False:
      visited[u]=True
      dfs(u)
  return 0

ans = 0
visited = [False]*N
for i in range(N):
  if visited[i]==False:
    visited[i]=True
    dfs(i)
    ans += 1
print(ans)

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

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

uf = UnionFind(N)

for _ in range(M):
  x,y,z = map(int, input().split())
  uf.union(x-1,y-1)
  
ans = len(uf.roots())
  
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

def common_divisor(n):
    cd = []
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            cd.append(i)
            if i != n//i:
                cd.append(n//i)
    return list(set(cd))

cd_dic = {}
for cd in common_divisor(A[0]):
    cd_dic[cd] = 1

for cd in common_divisor(A[1]):
    if cd not in cd_dic:
        cd_dic[cd] = 1
    else:
        cd_dic[cd] = 2
#print(cd_dic)
for k in cd_dic.keys():
    if cd_dic[k] == 2:
        cd_dic[k] = True
    else:
        cd_dic[k] = False
from copy import copy
for a in A[2:]:
    #print(cd_dic)
    d = copy(cd_dic)
    for k,v in cd_dic.items():
        if a%k!=0:
            if v == True:
                d[k] = False
            else:
                d.pop(k)
    cd_dic = copy(d)
ans = max(cd_dic.keys())
print(ans)

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

def common_divisor(n):
    cd = []
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            cd.append(i)
            if i != n//i:
                cd.append(n//i)
    return list(set(cd))

cd_dic = {}
for cd in common_divisor(A[0]):
    cd_dic[cd] = 1

for cd in common_divisor(A[1]):
    if cd not in cd_dic:
        cd_dic[cd] = 1
    else:
        cd_dic[cd] = 2
#print(cd_dic)
for k in cd_dic.keys():
    if cd_dic[k] == 2:
        cd_dic[k] = True
    else:
        cd_dic[k] = False
from copy import copy
for a in A[2:]:
    #print(cd_dic)
    d = copy(cd_dic)
    for k,v in cd_dic.items():
        if a%k!=0:
            if v == True:
                d[k] = False
            else:
                d.pop(k)
    cd_dic = copy(d)
ans = max(cd_dic.keys())
print(ans)