Harryxun/stf_run huggingface dataset:
def wa(h, w, f):
    if not (0 <= h <= H-1 and 0 <= w <= W-1):
        return
    elif mapp[h][w] != f:
        return
    else:
        mapp[h][w] = '$'
        wa(h, w+1, f)
        wa(h-1, w, f)
        wa(h, w-1, f)
        wa(h+1, w, f)

while True:
    H, W = map(int, raw_input().split(' '))
    if H == 0 and W == 0: break
    mapp = [list(raw_input()[i*W:i*W+W]) for i in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if mapp[h][w] == '@':
                wa(h, w, '@')
            elif mapp[h][w] == '#':
                wa(h, w, '#')
            elif mapp[h][w] == '*':
                wa(h, w, '*')
            else:
                continue
            count += 1
    else:
        print count

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)
def wa(h, w, f):
    if not (0 <= h < H and 0 <= w < W):
        return
    elif mapp[h][w] != f:
        return
    else:
        mapp[h][w] = '$'
        wa(h, w+1, f)
        wa(h-1, w, f)
        wa(h, w-1, f)
        wa(h+1, w, f)

while True:
    H, W = map(int, raw_input().split())
    if H == 0 and W == 0: break
    mapp = [list(raw_input()) for i in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if mapp[h][w] == '@':
                count += 1
                wa(h, w, '@')
            elif mapp[h][w] == '#':
                count += 1
                wa(h, w, '#')
            elif mapp[h][w] == '*':
                count += 1
                wa(h, w, '*')
    else:
        print count
import sys
def main():
    ans = [0] * 2
    for line in sys.stdin:
        try:
            a,b,c = map(int, line.split())
            if a ** 2 + b ** 2 == c ** 2:
                ans[0] += 1
            else:
                ans[1] += 1

        except EOFError:
            for a in ans:
                print(a)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def main():
    r = 0
    d = 0
    for line in sys.stdin:
        A = list(map(int, line.split(",")))
        if A[0] == A[1]:
            d += 1
        else:
            if A[0] ** 2 + A[1] ** 2 == A[2] ** 2:
                r += 1

    print(r)
    print(d)



if __name__ == "__main__":
    main()
from math import sqrt
from collections import Counter
import sys
import numpy as np

def factorize(n):
    rt = int(sqrt(n)+1)
    facts = []
    for i in range(2, rt+1):
        if n % i == 0:
            facts.append(i)
            while n % i == 0:
                n //= i
    if n != 1:
        facts.append(n)
    return facts

def sieve(n):
    S = [True] * (n+1)
    S[0] = S[1] = False
    i = 2
    while i * i <= n:
        if S[i]:
            k = i * i
            while k <= n:
                S[k] = False
                k += i
        i += 1
    return S


n = int(input())
A = list(map(int, input().split()))
amax = max(A)
primes= np.arange(amax+1)[sieve(amax)]


facts = {}
for a in A:
    rt = int(sqrt(a)+1)
    for p in primes:
        if p > rt: break
        if a % p == 0:
            if facts.get(p) is None:
                facts[p] = 1
            else:
                facts[p] += 1

p_max = max(facts.values()) if facts  else 1
if  p_max == 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

def arrayF(n): 
    F=[0]*(n+1) 
    i=2 
    while i*i<=n:
        if F[i] == 0: 
            k=i*i
            while k <= n:
                if F[k] == 0:
                    F[k] = i
                k += i
        i += 1 
    return F


def factorization(x, F): 
    primeFactors = []
    while F[x] > 0:
        primeFactors.append(F[x])
        x //= F[x] 
    if x != 1:
        primeFactors.append(x)
    return set(primeFactors)

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

amax = max(A)
F  = arrayF(amax)

P = [0] *  (amax+1)
for a in A:
    for p in factorization(a,  F):
        P[p] += 1
p_max = max(P)
if  p_max <= 1:
    print('pairwise coprime')
elif  p_max <  n:
    print('setwise coprime')
else:
    print('not coprime')
n = int(input())
a = list(input().split())
a.sort(reverse=True)
print(sum(a[0::2]) - sum(a[1::2]))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
print(sum(a[0::2]) - sum(a[1::2]))
N, M= map(int, input().split())
a_list = sorted(map(int, input().split()), reverse = True)

# インデックスを分かりやすくするために先頭に0を追加
match_num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [- 10 ** 5] * (N + 1)
dp[0] = 0

# 桁数を調べる
for i in range(1, N+1):
    dp[i] = max([dp[i - match_num[a]] + 1 for a in a_list])

# 各桁に使う数字を調べる
ans = [""] * dp[N]
rest_match = N
for i in range(dp[N]):
    for a in a_list:
        index = rest_match - match_num[a]
        if index >= 0 and dp[index] == dp[N] - i - 1:
            rest_match -= match_num[a]
            ans[i] = str(a)
            break
print("".join(ans))


### FIXED CODE ###

N, M= map(int, input().split())
a_list = sorted(map(int, input().split()), reverse = True)

# インデックスを分かりやすくするために先頭に0を追加
match_num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

inf = 10 ** 5
dp = [-inf] * (N + 1)
dp[0] = 0

# 桁数を調べる
for i in range(1, N+1):
    dp[i] = max([dp[i - match_num[a]] + 1 for a in a_list if i - match_num[a] >= 0] + [-inf])

# 各桁に使う数字を調べる
ans = [""] * dp[N]
rest_match = N
for i in range(dp[N]):
    for a in a_list:
        index = rest_match - match_num[a]
        if index >= 0 and dp[index] == dp[N] - i - 1:
            rest_match -= match_num[a]
            ans[i] = str(a)
            break
print("".join(ans))
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse = True)
while M > 0:
    A[0] //= 2
    for i in range(1,M):
        if A[i] >= A[0]:
            A[i] //= 2
        else:
            M -= i
            A.sort(reverse = True)
            break
    else:
        break
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse = True)
while M > 0:
    A[0] //= 2
    for i in range(1,M):
        if i < N and A[i] >= A[0]:
            A[i] //= 2
        else:
            M -= i
            A.sort(reverse = True)
            break
    else:
        break
print(sum(A))
def solve():
    n,k = map(int, infile.readline().split())
    da = list(map(int,infile.readline().split()))
    infile.close()
    ans = 1
    MOD = 10**9+7
    
    if n == k:
        for i in range(n):
            ans = ans*da[i]%MOD
        return ans
    
    neg = []
    pos = []
    for i in range(n):
        if da[i] < 0:
            neg.append(da[i])
        else:
            pos.append(da[i])
    neg.sort()
    pos.sort()
    
    if len(pos) == 0 and k%2 == 1:
        neg.reverse()
        for i in range(k):
            ans = ans * da[i] % MOD
        return ans
    
    li = []
    pos.reverse()
    po, ne = 0, 0
    if k%2 == 1:
        po = 1
        ans = pos[0]
    while po+1 < len(pos):
        li.append(pos[po]*pos[po+1])
        po += 2
    while ne+1 < len(neg):
        li.append(neg[ne]*neg[ne+1])
        ne += 2
    li.sort()
    li.reverse()
    for i in range(k//2):
        ans = li[i] * ans % MOD
    return ans

if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

def solve():
    n, k = NextInts()
    da = NextIntList()
    ans = 1
    MOD = 10**9+7
    
    if n == k:
        for i in range(n):
            ans = ans*da[i]%MOD
        return ans
    
    neg = []
    pos = []
    for i in range(n):
        if da[i] < 0:
            neg.append(da[i])
        else:
            pos.append(da[i])
    neg.sort()
    pos.sort()

    if len(pos) == 0 and k%2 == 1:
        neg.reverse()
        for i in range(k):
            ans = ans * neg[i] % MOD
        return ans
    
    pos.reverse()
    li = []
    po, ne = 0, 0
    if k%2 == 1:
        po = 1
        ans = pos[0]
    while po+1 < len(pos):
        li.append(pos[po]*pos[po+1])
        po += 2
    while ne+1 < len(neg):
        li.append(neg[ne]*neg[ne+1])
        ne += 2
    li.sort()
    li.reverse()
    for i in range(k//2):
        ans = li[i] * ans % MOD
    return ans

if __name__ == "__main__":
    print(solve())
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

A,B,K = [int(x) for x in input().split()]
ls =[i for i in range(1,A+1) if A % i == 0 and B % i == 0]
print(ls[K])

### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

A,B,K = [int(x) for x in input().split()]
ls =[i for i in range(1,A+1) if A % i == 0 and B % i == 0]
ls.reverse()
answer = ls[K-1]
print(answer)
N = int(input())
Atmp = [0] + list(map(int, input().split()))
A = {}

for i,a in enumerate(Atmp):
    A[i] = a

#print(A)

X = {}

def umeru(X, M, last):
    #print('---')
    for i in reversed(list(range(N//(M+1)+1, N//M+1))):
        if M == 1:
            X[i] = A[i]
        else:
            Xsum = 0
            j = 2
            while(i*j < N):
                Xsum += X[i*j]
                j += 1
                continue
            odd = Xsum % 2
            #print(M, i, odd, A[i])
            if odd == A[i]:
                X[i] = 0
            else:
                X[i] = 1
    #print(N,M,X)
    if last:
        return
    if N//(M+1) == 0:
        umeru(X, M+1, True)
    else:
        umeru(X, M+1, False)

umeru(X, 1, False)
print(X)

M = 0
for i in range(1, N+1):
    if X[i] == 1:
        M += 1

print(M)

for i in range(1, N+1):
    if X[i] == 1:
        print(i, end=' ')


print()


### FIXED CODE ###

import sys

N = int(input())
Atmp = [0] + list(map(int, input().split()))
A = {}

for i,a in enumerate(Atmp):
    A[i] = a

#print(A)

X = {}

for i in reversed(list(range(1,N+1))):
    Xsum = 0
    j = 2
    while(i*j <= N):
        Xsum += X[i*j]
        j += 1
        continue
    odd = Xsum % 2
    if odd == A[i]:
        X[i] = 0
    else:
        X[i] = 1
    
M = 0
for i in range(1, N+1):
    if X[i] == 1:
        M += 1

print(M)
if M == 0:
    sys.exit()

xxx = []
for i in range(1, N+1):
    if X[i] == 1:
        xxx.append(str(i))

print(' '.join(xxx))
if __name__ = "__main__":
  S = input() # sを取得し、strに値を入れる
  if S == "ABC":
    print "ARC"
  elif S == "ARC":
    print "ABC"
  

### FIXED CODE ###

if __name__ == "__main__":
  S = input() # sを取得し、strに値を入れる
  if S == "ABC":
    print("ARC")
  elif S == "ARC":
    print("ABC")
N , M ,X = map(int,input().split())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
ans = []
for i in range(2 ** N):
    rikai = [0 for _ in range(M)]
    cost = 0
    for b in range(N):
        if i  & (1 <<  b):
            for x in range(1,M + 1):
                rikai[x-1] += L[b][x] 
            cost += L[b][0]
    for x in rikai:
        if x < X: break
    else:
        ans.append(cost)

print(min(ans))


### FIXED CODE ###

N , M ,X = map(int,input().split())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
ans = []
for i in range(2 ** N):
    rikai = [0 for _ in range(M)]
    cost = 0
    for b in range(N):
        if i  & (1 <<  b):
            for x in range(1,M + 1):
                rikai[x-1] += L[b][x] 
            cost += L[b][0]
    for x in rikai:
        if x < X: break
    else:
        ans.append(cost)
try:
    print(min(ans))
except:
    print(-1)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

cnt_a, cnt_b = sum(a), sum(b)
ans = "No"
i = 0
cnt = 0
while cnt < cnt_b - cnt_a:
    if a[i] < b[i]:
        cnt += int((b[i] - a[i]) / 2 + 0.5)
    else:
        cnt += a[i] - b[i]
    i += 1
    if i == n:
        ans = "Yes"

print(ans)


### FIXED CODE ###

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

x, y = 0, 0
for i in range(n):
    dif = b[i] - a[i]
    if dif > 0:
        x += dif // 2
    else:
        y += -dif

print("Yes" if x >= y else "No")
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

for _ in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    a[x].append(y)
    a[y].append(x)

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

for _ in range(m):
    x,y,z = map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)
print(res)
A,B,K = map(int,input().split())
L = list(range(A,B + 1))
for i in range(len(L)):
  if i < K or len(L) - K <= i:
    print(L[i])


### FIXED CODE ###

A,B,K = map(int,input().split())
if B - A >= 2 * K :
  for i in range(K):
    print(A + i)
  for j in reversed(range(K)):
    print(B - j)
else:
  for _ in range(A,B + 1):
    print(_)
import sys
from collections import deque
from scipy.special import comb

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	X,Y = MI()
	N3 = (2*Y-X)
	M3 = (2*X-Y)
	if(N3%3!=0 or M3%3!=0 or N3 < 0 or M3<0):
		print(0)
	else:
		N=N3//3
		M=M3//3

		K = min(N,M)

		def cmb(n, r, mod):
			if ( r<0 or r>n ):
				return 0
			r = min(r, n-r)
			return g1[n] * g2[r] * g2[n-r] % mod

		mod = 10**9+7 #出力の制限
		L = 10**6
		g1 = [1, 1] # 元テーブル
		g2 = [1, 1] #逆元テーブル
		inverse = [0, 1] #逆元テーブル計算用テーブル

		for i in range( 2, L + 1 ):
			g1.append( ( g1[-1] * i ) % mod )
			inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
			g2.append( (g2[-1] * inverse[-1]) % mod )

		print(cmb(N+M,K,mod))


main()

### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	X,Y = MI()
	N3 = (2*Y-X)
	M3 = (2*X-Y)
	if(N3%3!=0 or M3%3!=0 or N3 < 0 or M3<0):
		print(0)
	else:
		N=N3//3
		M=M3//3

		K = min(N,M)

		def cmb(n, r, mod):
			if ( r<0 or r>n ):
				return 0
			r = min(r, n-r)
			return g1[n] * g2[r] * g2[n-r] % mod

		mod = 10**9+7 #出力の制限
		L = 10**6
		g1 = [1, 1] # 元テーブル
		g2 = [1, 1] #逆元テーブル
		inverse = [0, 1] #逆元テーブル計算用テーブル

		for i in range( 2, L + 1 ):
			g1.append( ( g1[-1] * i ) % mod )
			inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
			g2.append( (g2[-1] * inverse[-1]) % mod )

		print(cmb(N+M,K,mod))


main()
n=int(input())
t=list(map(int,input().split()))
m=int(input())
p,x=[],[]
for _ in range(m):
  _p,_x=map(int,input().split())
  p.append(_p)
  x.append(_x)
s=sum(t)
for i in range(m):
  print(s-t[p[i]]+x[p[i]])


### FIXED CODE ###

n=int(input())
t=list(map(int,input().split()))
m=int(input())
p,x=[],[]
for _ in range(m):
  _p,_x=map(int,input().split())
  p.append(_p-1)
  x.append(_x)
s=sum(t)
for i in range(m):
  print(s-t[p[i]]+x[i])
#!/usr/bin/env python

import math

n=int(raw_input().strip())
N=int(math.ceil(math.sqrt(float(n))))
a=[]
for i in range(1,N+1):
    if n%i==0:
        a.append(i)
A=max(a)
B=int(n/A)
A_keta=len(map(int,str(A)))
B_keta=len(map(int,str(B)))
F=max(A_keta,B_keta)
print F


### FIXED CODE ###

A,B=map(int,raw_input().split())
print (A+B)%24
A,B,X=map(int,input().split())
a=[]
for i in range(1,10):
  rest=X-B*i
  if rest>0 and len(str(int(rest/A)))==i:
      a.append(rest//A)
a.sort()
if a==[]:
    print(0)
else:
    print(a[len(a)-1])

### FIXED CODE ###

S=input()
if S=="SUN":
  print(7)
elif S=="MON":
  print(6)
elif S=="TUE":
  print(5)
elif S=="WED":
  print(4)
elif S=="THU":
  print(3)
elif S=="FRI":
  print(2)
elif S=="SAT":
  print(1)
N=int(input())
S=list(input())
S_ptn1=S[::-1]
cnt=0
cnt_ptn1=0
for i in range(N-1):
    if S[i]=='#' and S[i+1]=='.':
        S[i+1]='#'
        cnt+=1
for i in range():
    if S_ptn1[i]=='.' and S_ptn1[i+1]=='#':
        S[i+1]='.'
        cnt_ptn1+=1
if cnt<cnt_ptn1:
    print(cnt)
else:
    print(cnt_ptn1)

### FIXED CODE ###

from itertools import accumulate
N=int(input())
S=input()
black=[0]*N
white=[0]*N
for i,s in enumerate(S):
        if s=='#':
                black[i]=1
        else:
                white[i]=1
black = [0] + black
black = list(accumulate(black))
white = [0] + white[::-1]
white = list(accumulate(white))[::-1]
ans=[]
for i in range(N+1):
        ans.append(black[i]+white[i])
print(min(ans))
# coding: utf-8
n = int(input())
al = sorted(list(set(int(i) for i in input().split())))
bl = sorted(list(set(int(i) for i in input().split())))
cl = sorted(list(set(int(i) for i in input().split())))
ans = 0

def search(ar, key, flag):
    left = -1
    right = len(ar)
    center = (left + right) // 2
    
    while right - left > 1:
        if ar[center] == key:
            if flag == 0:
                return center
            elif flag == 1:
                return len(ar)-1-center
        elif ar[center] < key:
            left = center
            center = (left + right) // 2
        else:
            right = center
            center = (left + right) // 2
    
    if flag == 0:
        return right
    elif flag == 1:
        return len(ar) - right
        

for i in range(n):
    mid = bl[i]
    top_num = search(al, mid, 0)
    bottom_num = search(cl, mid, 1)
    ans += top_num * bottom_num
    
print(ans)

### FIXED CODE ###

# coding: utf-8
n = int(input())
al = sorted(list(int(i) for i in input().split()))
bl = sorted(list(int(i) for i in input().split()))
cl = sorted(list(int(i) for i in input().split()))
ans = 0

def low_left(a, key):
    left = -1
    right = len(a)
    while right - left > 1:
        center = (left + right) // 2
        if a[center] >= key:
            right = center
        else:
            left = center
    return left+1 
    
def high_right(a, key):
    left = -1
    right = len(a)
    while right - left > 1:
        center = (left + right) // 2
        if a[center] <= key:
            left = center
        else:
            right = center
    return n-right
    
for i in bl:
    ans += low_left(al, i) * high_right(cl, i)

print(ans)
# AtCorder-Candy Distribution Again

n,x = map(int, input().split())
list[] = list(map(int, input().split()))

a = 0
i = 0
list.sort()

if x < list[0]:
    print(0)

elif x >= list[0]:

    while x >= list[i] and x > 0:
        x -= list[i]
        a += 1
        if i < n-1 and x < list[i+1]:
            break
        if i == n-1:
            if x > list[i]:
                a = n-1
            else:
                a = n
            break
        i += 1

    print(a)

    

### FIXED CODE ###

n,x = map(int, input().split())
list = list(map(int, input().split()))

a = 0
i = 0

list.sort()

if list[0] > x:
    print(0)

elif x > sum(list):
    print(n-1)

else:
    while x > 0 and x >= list[i]:
        x -= list[i]
        i += 1
        a += 1
        if i == n:
            break

    print(a)
num == int(input())
num_1 == num % 10
if num_1 == 3:
  print('bon')
elif num_1 <= 1 or num_1 == 6 or num_1 == 8:
  print('pon')
else:
  print('hon')

### FIXED CODE ###

num = int(input())
num_1 = num % 10
if num_1 == 3:
  print('bon')
elif num_1 <= 1 or num_1 == 6 or num_1 == 8:
  print('pon')
else:
  print('hon')
import math
import decimal
decimal.getcontext().prec = 6
a, b, c = map(int, input().split())
a = decimal.Decimal(a)
b = decimal.Decimal(b)
c = decimal.Decimal(c)
if a + 2 * math.sqrt(a*b) + b - c < 1e-20:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

d = c - a - b
if d**2 > 4*a*b and d > 0:
# if a + 2 * d +b - c < 1e-20:
    print("Yes")
else:
    print("No")
N, K = map(int, input().split())
Nm = N % K
ans = Nm
A = [0]*(K+1)
A[Nm] = 1
while 1:
    if ans == 0:
        break
    elif A[abs(Nm-K)] != 1:
        if abs(Nm-K) < ans:
            ans = abs(Nm-K)
        A[abs(Nm-K)] = 1
        Nm = abs(Nm-K)
    else:
        break
    
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
Nm = N % K
ans = Nm
A = [Nm]
while 1:
    if ans == 0:
        break
    elif abs(Nm-K) in A:
        break
    else:
        if abs(Nm-K) < ans:
            ans = abs(Nm-K)
        A.append(abs(Nm-K))
        Nm = abs(Nm-K)
    
print(ans)
import sys
if sys.version_info[0] == 2:
    input = raw_input

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        if w % 2 == 0:
            tonari_c = jibun_c
        else:
            tonari_c = 1 - jibun_c

        dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()
        

### FIXED CODE ###

import sys
if sys.version_info[0] == 2:
    input = raw_input
sys.setrecursionlimit(2 ** 31 -1)

res = None
G = None

def dfs(jibun_v, p, jibun_c):
    global res
    global G

    res[jibun_v] = jibun_c
    #print(jibun_v, p, jibun_c)

    tonari_nodes = G[jibun_v]
    for tonari_v, w in tonari_nodes:
        #if tonari_v == p: # only no loop
        #if tonari_v == p or res[tonari_v] != -1:
        if res[tonari_v] != -1:
            continue

        else:
            if w % 2 == 0:
                tonari_c = jibun_c
            else:
                tonari_c = 1 - jibun_c

            dfs(tonari_v, jibun_v, tonari_c)
    

def main():
    N= int(input())

    global G
    G = [[] for _ in range(N)]

    for i in range(N-1):
        u, v, w = map(int, input().split(" "))
        u -= 1
        v -= 1
        w = w % 2
        G[u].append([v, w])
        G[v].append([u, w])

    global res
    res = [-1 for _ in range(N)]
    
    jibun_v = 0
    p = -1
    jibun_c = 0
    dfs(jibun_v, p, jibun_c)

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

main()