Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
memo=set()
n=input()
g=0
l=list(map(int,input().split()))
for i in l:
    g=gcd(i,g)
if g!=1:print('not coprime');exit()

for i in l:
    for p in primeFactor(i):
        if p in memo:print("setwise coprime");exit()
        memo.add(p)
print("pairwise coprime")

### FIXED CODE ###

n,a=int(input()),list(map(int,input().split()))
g=0
from math import gcd
for i in a:g=gcd(i,g)
if g!=1:print("not coprime")
else:
    from collections import defaultdict
    memo=defaultdict(int)
    for i in a:
        for p in range(2,int(i**.5)+1):
            if i%p==0:
                while i%p==0:i//=p
                if memo[p]:
                    print("setwise coprime");exit()
                memo[p]+=1
        if i!=1:
            if memo[i]:print("setwise coprime");exit()
            memo[i]+=1
    print("pairwise coprime")
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
D=[0]*2019
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
es = defaultdict(set)
h = defaultdict(int)
for i, a in enumerate(A):
    for j, k in zip(a, a[1:]):
        a, b = (i, j) if i < j else (j, i)
        c, d = (i, k) if i < k else (k, i)
        if not (c, d) in es[(a, b)]:
            es[(a, b)].add((c, d))
            h[(c, d)] += 1
dq = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if h[(i, j)] == 0:
            dq.append(((i, j), 1))
cnt, day = 0, defaultdict(int)
while len(dq) > 0:
    cnt += 1
    p, d = dq.popleft()
    if d < day[p]:
        continue
    for q in es[p]:
        h[q] -= 1
        if h[q] == 0:
            dq.append((q, d+1))
            day[q] = max(day[q], d+1)
ans = max(day.values()) if cnt == N*(N-1)//2 else -1
print(ans)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.6:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [1]
for i in range(n):
    b.append(a[i]*b[-1])
c = [b[i+k]/b[i] for i in range(n-k+1)]
for i in range(len(c) - 1):
    if c[i+1] > c[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
    if a[i] < a[i+k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N, Y = map(int, input().split())
# i: man, j: gosen, k: sen
output_flag=0
man = -1
gosen = -1
sen = -1
for i in range(0, N+1):
    while output_flag==0:
        for j in range(0, N+1-i):
            k = N-i-j
            total = 10000*i+5000*j+1000*k
            if total==Y:
                output_flag=1
                man = i
                gosen = j
                sen = k
                break
    if output_flag==1:
        break
print(man, gosen, sen)

### FIXED CODE ###

N, Y = map(int, input().split())
man = -1
gosen = -1
sen = -1
for i in range(0, N+1):
    for j in range(0, N+1-i):
        k = N-i-j
        total = 10000*i+5000*j+1000*k
        if total==Y:
            man = i
            gosen = j
            sen = k
print(man, gosen, sen)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
p=x.count("1")
minus=0
plus=0
for i in range(n):
    if x[-i-1]=="1":
        plus+=2**i
        plus%=(p+1)
if p!=1:
    for i in range(n):
        if x[-i-1]=="1":
            minus+=2**i
            minus%=(p-1)

def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

for i in range(n):
    if x[i]=="0":
        amari=(plus+2**(n-i-1)%(p+1))%(p+1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)
    else:
        if p==1:
            print(0)
            continue
        amari=(minus-2**(n-i-1)%(p-1))%(p-1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
x10=int(x,2)
pcx=x.count("1")

plus=x10%(pcx+1)
if pcx>=2:
    minus=x10%(pcx-1)

def popcnt(x):
    cnt=1
    while x>=1:
        x%=(bin(x).count("1"))
        cnt+=1
    return cnt

for i in range(n):
    if x[i]=="0":
        amari=(plus+pow(2,n-i-1,pcx+1))%(pcx+1)
        print(popcnt(amari))
    else:
        if pcx==1:
            print(0)
        else:
            amari=(minus-pow(2,n-i-1,pcx-1))%(pcx-1)
            print(popcnt(amari))
### BUGGY CODE ###

import math
def factorization(n):
    arr = []
    temp = n
    num = 0
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    
    return math.prod([f[1]+1 for f in arr])
if __name__ == "__main__":
    N = int(input())
    ans = 0
    for i in range(1, N+1):
        ans += i*factorization(i)
    print(ans-1)

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    ans = 0
    for i in range(1, N+1):
        Y = N//i
        ans += Y*(Y+1)*i//2
    print(ans)
### BUGGY CODE ###

N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for ai in range(N):
  for bi in range(ai+1,N):
    for ci in range(bi+1,N):
      if L[ci] < L[ai] + L[bi]:
        ans += 1
print(ans)

### FIXED CODE ###

import bisect 
N = int(input())
L = sorted(list(map(int,input().split())))
ans = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    idx = bisect.bisect(L,L[i]+L[j]-1)
    ans += idx-j-1
print(ans)
### BUGGY CODE ###

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

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

for i in range(M):
    A = heapsort(A)
    A[N-1] //= 2

print(sum(A))

### FIXED CODE ###

import heapq
import math

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

# 各要素に1掛ける
A = list(map(lambda x: x * -1, A))
heapq.heapify(A)

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

print(sum(A) * -1)
### BUGGY CODE ###

n,a,b=map(int,input().split())
ans=0
while n>0:
    if n-a<0:
        ans=ans+n
        break
    n=n-a
    ans=ans+a
    n=n-b
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
if n<a:
    print(n)
    exit()
katamari=max(n//(a+b),1)
if n>a+b:
    amari=min(n%(a+b),a)
else:
    amari=0
print(a*katamari+amari)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, raw_input().split())
line = []   # 定期便
for i in range(M):
    a, b = map(int, raw_input().split())
    line.append([a, b])

for l in line:
    if l[0] == 1:
        for k in line:
            if k[0] == l[1] and k[1] == N:
                print 'POSSIBLE'
                exit()

print 'IMPOSSIBLE'


### FIXED CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, raw_input().split())
start, finish = [], []
for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        start.append(b)
    elif b == N:
        finish.append(a)

if set(start) & set(finish):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'
### BUGGY CODE ###

#!/usr/bin/env pypy
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, readline().split())
    # a = readlines()
    a = list(map(int, readlines()))
    # diff_a = [a[i+1] - a[i] for i in range(m - 1)]
    # if 1 in diff_a:
    #     print(0)
    #     return
    p1, p2 = 0, 1
    if 1 not in a:
        p1 = 1

    for i in range(2, n + 1):
        if i in a:
            p1, p2 = 0, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1

    print(p1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
A = list(map(int, readlines()))
assert len(A) == M

MOD = 10 ** 9 + 7


def solve():
    broken = [False] * (N + 1)
    for a in A:
        broken[a] = True
    p1, p2 = 1, 0
    for i in range(1, N + 1):
        if broken[i]:
            p1, p2 = 0, p1
        elif i == 1:
            p1, p2 = p1, p1
        else:
            p1, p2 = (p1 + p2) % MOD, p1
    return p1


if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

S = input()[::-1]

dp = [[1]+[0]*12]
MOD = 10**9+7

for i in range(1,len(S)+1):
  s = S[i-1]
  dp += [[0]*13]
  if s=='?':
    for j in range(13):
      for h in range(10):
        x = h*(10**(i-1))%13
        dp[i][(j+x)%13] += dp[i-1][j]
    for j in range(13):
      dp[i][j] = dp[i][j]%MOD
  else:
    c = int(s)
    x = c*(10**(i-1))%13
    for j in range(13):
      dp[i][(j+x)%13] = dp[i-1][j]
    for j in range(13):
      dp[i][j] = dp[i][j]%MOD
print(dp[-1][5])

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            i = (_r + r) % 13
            tdp[i] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

import sys
from itertools import groupby

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def len_count(S):
    H, W = len(S), len(S[0])
    L = [[0] * W for _ in range(H)]
    for i, row in enumerate(S):
        idx = 0
        for k, g in groupby(list(row)):
            n = len(list(g))
            if k == '.':
                L[i][idx : idx + n] = [n] * n
            idx += n
    return L


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L1 = len_count(S)
    L2 = list(zip(*len_count(list(zip(*S)))))

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L1[i][j] + L2[i][j] - 1)

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import groupby

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def len_count(S):
    H, W = len(S), len(S[0])
    L = [[0] * W for _ in range(H)]
    for row_S, row_L in zip(S, L):
        vec = [1]
        for i in range(1, W):
            if row_S[i - 1] == row_S[i]:
                vec[-1] += 1
            else:
                vec.append(1)

        idx = 0
        valid = row_S[0] == '.'
        for n in vec:
            if valid:
                for i in range(idx, idx + n):
                    row_L[i] = n
            idx += n
            valid = not valid

    return L


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L1 = len_count(S)
    L2 = len_count(list(zip(*S)))

    ans = 0
    for i in range(H):
        for j in range(W):
            if ans < L1[i][j] + L2[j][i] - 1:
                ans = L1[i][j] + L2[j][i] - 1

    print(ans)
    return


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC = sorted(BC, key=lambda x: -x[1])

extend = A.extend
[extend([BC[i][1]] * BC[i][0]) for i in range(m)]

A = sorted(A, reverse=True)
print(sum(A[:n]))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dictA = {}
for i in a:
  if not(i in dictA.keys()):
    dictA[i] = a.count(i)

sdict = sorted(dictA.values())
ans = 0
for i in range(len(sdict) - k):
  ans += sdict[i]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
p =  [0] * (n + 1)
for i in a:
  p[i] += 1
p.sort()
print(sum(p[:n-k+1]))
### BUGGY CODE ###

n =int(input())
x = list(map(int, input().split()))
if x.count(0) !=0:
  print('0')
else:  
  ans=1
  for i in range(n):
    ans=ans*x[i]
  if ans >10**18:
    print(-1)
  else:
    print(ans)  
    

### FIXED CODE ###

n =int(input())
x = list(map(int, input().split()))
if x.count(0) !=0:
  print('0')
else:  
  ans=x[0]
  for i in range(1,n):
    ans=ans*x[i]
    if ans >10**18:
      print(-1)
      exit()
  print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0 for _ in range(n-1)]
MOD = 10**9+7
   
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  dp[i+2] %= MOD

print(dp[-1])  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

print(dp[-1])
### BUGGY CODE ###

import math


def gcd(a, b, c):
    w = math.gcd(a, b)
    return math.gcd(w, c)


k = int(input())
answer = 0
for w_a in range(1, k + 1):
    for w_b in range(1, k + 1):
        for w_c in range(1, k + 1):
            answer += gcd(w_a, w_b, w_c)

print(answer)


### FIXED CODE ###

import math


k = int(input())
answer = 0
for w_a in range(1, k + 1):
    for w_b in range(1, k + 1):
        w = math.gcd(w_a, w_b)
        for w_c in range(1, k + 1):
            answer += math.gcd(w, w_c)

print(answer)
### BUGGY CODE ###

import math


N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [10**9] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
    for j in range(1, K + 1):
        if i - j < 0:
            break

        dp[i] = min(
            dp[i],
            dp[i - j] + abs(h[i] - h[i - j])
        )

print(dp[-1])


### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
h = np.array([int(i) for i in input().split()])
dp = np.full(N, 10 ** 10)

# 初期条件
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
    ik = max(0, i - K)
    dp[i] = np.min(dp[ik:i] + np.abs(h[i] - h[ik:i]))

print(int(dp[-1]))
### BUGGY CODE ###

from collections import defaultdict
from queue import Queue
n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [MX for i in range(n)]
reached = [False for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s] = 0

q = Queue()
q.put(s)
while not q.empty():
    node = q.get()
    reached[node] = True
    for next_node in edge[node]:
        for nnext_node in edge[next_node]:
            for nnnext_node in edge[nnext_node]:
                if not reached[nnnext_node]: q.put(nnnext_node)
                dist[nnnext_node] = min(dist[nnnext_node], dist[node] + 1)

if dist[t] == MX:
    print(-1)
else:
    print(dist[t])



### FIXED CODE ###

from collections import defaultdict
from queue import Queue

n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [[MX, MX, MX] for i in range(n)]
reached = [[False, False, False] for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s][0] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        reached[next_node][next_step] = True
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

if dist[t][0] == MX:
    print(-1)
else:
    print(dist[t][0])
### BUGGY CODE ###

class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [0] * (n + 1), [0] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a] += 1
        fr[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: [] for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c] += 1 if d in mp[uf.t[c]] else 0
        br[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - 1 - fr[i] - br[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(len, fr)
    *g, = map(set, g)
    *gn, = map(len, g)
    return " ".join([
        str(gn[mp[uf.t[i]]] - 1 - fr[i] - sum(j in g[mp[uf.t[i]]]
                                              for j in br[i]))
        for i in range(1, n + 1)
    ])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

def main():
    import collections
    import sys
    input = sys.stdin.readline
    N = int(input())
    uvw = [map(int, input().split()) for i in range(N-1)]

    G = [[-1]*N for i in range(N)]
    for u, v, w in uvw:
        u -= 1
        v -= 1
        G[u][v] = w
        G[v][u] = w
    q = collections.deque()
    q.append((0, 0))
    s = set(range(1, N))
    ans = [0]*N
    while(q):
        x, a = q.popleft()
        tmp = set()
        for y in s:
            if G[x][y] > 0:
                q.append((y, a+G[x][y]))
                ans[y] = (a+G[x][y]) % 2
                tmp.add(y)
        s -= tmp
    print(*ans, sep="\n")


main()


### FIXED CODE ###

import collections
N = int(input())
d = [0]*N
route = [set() for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    route[u].add((v, w))
    route[v].add((u, w))
    d[u] += 1
    d[v] += 1
d = d.index(max(d))
q = collections.deque()
q.append((d, 0))

G = [0]*N

while(q):
    x, l = q.popleft()
    for v, w in route[x]:
        G[v] = w + l
        q.append((v, w+l))
        route[v].remove((x, w))
ans = [0]*N

for i in range(N):
    if i == d:
        continue
    if G[i] % 2 == 1:
        ans[i] = 1
for i in range(N):
    print(ans[i])