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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

MOD = 10**9+7
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = [[] for _ in range(n)]
seen = [False]*n
dp = [0]*n
def dfs(v):
  cnt = 1
  seen[v] = True
  for nv in T[v]:
    if seen[nv]:
      continue
    C[v].append(nv)
    cnt += dfs(nv)
  dp[v] = cnt
  return cnt

dfs(0)

p = [1]*(n+1)
inv = [1]*(n+1)
inv_two = pow(2, MOD-2, MOD)
for i in range(n):
  p[i+1] = p[i] * 2 % MOD
  inv[i+1] = inv[i] * inv_two % MOD
ans = 0
for i in range(n):
  s = 1
  t = 1
  cnt = 1
  for c in C[i]:
    l = dp[c]
    s *= inv[l]
    s %= MOD
    t += p[l] - 1
    t %= MOD
    cnt += l
  r = n - cnt
  s *= inv[r]
  s %= MOD
  t += p[r] - 1
  t %= MOD
  res = (1 - s*t) % MOD * inv_two
  res %= MOD
  ans += res
  ans %= MOD
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def main():
  MOD = 10**9+7
  n = int(input())
  T = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
  C = [[] for _ in range(n)]
  seen = [False]*n
  dp = [0]*n
  def dfs(v):
    cnt = 1
    seen[v] = True
    for nv in T[v]:
      if seen[nv]:
        continue
      C[v].append(nv)
      cnt += dfs(nv)
    dp[v] = cnt
    return cnt

  dfs(0)

  p = [1]*(n+1)
  inv = [1]*(n+1)
  inv_two = pow(2, MOD-2, MOD)
  for i in range(n):
    p[i+1] = p[i] * 2 % MOD
    inv[i+1] = inv[i] * inv_two % MOD
  ans = 0
  for i in range(n):
    s = 1
    t = 1
    cnt = 1
    for c in C[i]:
      l = dp[c]
      s *= inv[l]
      s %= MOD
      t += p[l] - 1
      t %= MOD
      cnt += l
    r = n - cnt
    s *= inv[r]
    s %= MOD
    t += p[r] - 1
    t %= MOD
    res = (1 - s*t) % MOD * inv_two
    res %= MOD
    ans += res
    ans %= MOD
  print(ans)

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

n=int(input())
a=list(map(int,input().split()))
b=list(set(a))   
if len(b)==1:
    print(b[0])
    exit()
else: 
    x=1
    while x>0:
        c=sorted(b)
        c[1]=c[1]-c[0]
        c=sorted(list(set(c)))
        if c[0]==1:
            x=0
        if len(c)==1:
            print(2)
            exit()
print(1)
            
    




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(set(a))   
if len(b)==1:
    print(b[0])
    exit()
else:
    c=sorted(b)
    x=1
    while x>0:
        v=c[0]
        for i in range(len(c)):
            if i!=0:
                c[i]=c[i]%v
        while 0 in c:
            c.remove(0)
        c=sorted(list(set(c)))
        if len(c)==1:
            print(c[0])
            exit()
        if c[0]==1:
            x=0
print(1)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = floyd_warshall(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))


### FIXED CODE ###

N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [0 for _ in range(13)]
  if s[-1] == '?':
    for i in range(10):
      sd[i] = 1
  else:
    sd[int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    tmpd = [0 for _ in range(13)]
    if _s != '?':
      rem = int(_s) * pow(10, i) % 13
      for j in range(13):
        tmpd[(j+rem)%13] = sd[j]
    else:
      for k in range(10):
        rem = k * pow(10, i) % 13
        for j in range(13):
          tmpd[(j+rem)%13] += sd[j]
          tmpd[(j+rem)%13] %= MOD
    sd = tmpd[:]
  print(sd[5])


if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [[0 for _ in range(13)] for _ in range(len(s))]
  if s[-1] == '?':
    for i in range(10):
      sd[0][i] = 1
  else:
    sd[0][int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    if _s != '?':
      rem = int(_s) * pow(10, i, 13) % 13
      for j in range(13):
        sd[i][(j+rem)%13] = sd[i-1][j]
    else:
      for k in range(10):
        rem = k * pow(10, i, 13) % 13
        for j in range(13):
          sd[i][(j+rem)%13] += sd[i-1][j]
          sd[i][(j+rem)%13] %= MOD
  print(sd[len(s)-1][5])


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

N, K = map(int, input().split())
ab = []
for i in range(N-1):
  a, b = map(int, input().split())
  ab.append((a-1, b-1))
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = []
  for j in range(N-1):
    a, b = ab[j]
    if a == i:
      js.append(b)
    elif b == i:
      js.append(a)
  jsn = list(filter(lambda j: not(counts[j]), js))
  #print(js, jsn)
  c = K-1-len(js)+len(jsn)
  for j in jsn:
    counts[j] = True
    r = (r*c)%1000000007
    c -= 1
  q.extend(jsn)
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)
### BUGGY CODE ###

import sys
def frog2(N,h,k):
    dp=[sys.maxsize-1]*N
    dp[0]=0
    for i in range(N):
        for j in range(i+1,i+k+1):
            if j<N:
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    return dp[N-1]

N,k=map(int,input().split())
h=list(map(int,input().split()))
print(frog2(N,h,k))

### FIXED CODE ###

import sys
def frog2(N,h,k):
    dp=[sys.maxsize-1]*N
    dp[0]=0
    for i in range(N):
        for j in range(i+1,i+k+1):
            if j<N:
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    return dp[N-1]

N,k=map(int,input().split())
h=list(map(int,input().split()))
print(frog2(N,h,k))
### BUGGY CODE ###

from collections import deque
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        tv_append=toVis.append
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                tv_append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    tv_append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()


    
            


### FIXED CODE ###

h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

import sys

n_in = input()
result = input().split()
total = 0
n_in = int(n_in)

for k0 in range(n_in):
    count = 0
    for l0 in range(k0):
        if int(result[k0]) <= int(result[l0]):
            count += 1
    if count == k0:
        total += 1

print(total)


### FIXED CODE ###

import sys

n_in = input()
result = input().split()
total = 0
n_in = int(n_in)
p_min = int(result[0])
for k0 in range(n_in):
    count = 0
    if int(result[k0]) <= p_min:
        total += 1
        p_min = int(result[k0])

print(total)
### BUGGY CODE ###

from functools import reduce
N = int(input())
mul = reduce(lambda x,y: x*y, map(int, input().split()))
res = mul if mul <= 10 ** 18 else -1
print(res)

### FIXED CODE ###

from functools import reduce
N = int(input())
A = [*map(int, input().split())]

if 0 in A:
    print(0)
    exit()

mul = 1
for n in A:
    mul *= n
    if mul > 10 ** 18:
        print(-1)
        exit()
print(mul)
### BUGGY CODE ###

def main():
    S=input()
    MOD=10**9+7
    dp={0:1,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
    for i in range(len(S)):
        new_dp={0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
        s=S[-1-i]
        if s=="?":
            for j in range(10):
                rem=(j*10**i)%13
                for k in range(13):
                    new_dp[(k+rem)%13]+=dp[k]
        else:
            rem=(int(s)*10**i)%13
            for k in range(13):
                new_dp[(k+rem)%13]+=dp[k]
        for l in range(13):
            new_dp[l]%=MOD
        dp=new_dp
    print(dp[5])
if __name__=="__main__":
    main()

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[0]*13
dp[0]=1
r=1
for i in range(len(S)):
    new_dp=[0]*13
    s=S[-1-i]
    if s=="?":
        for j in range(10):
            rem=(j*r)%13
            for k in range(13):
                new_dp[(k+rem)%13]+=dp[k]
    else:
        rem=(int(s)*r)%13
        for k in range(13):
            new_dp[(k+rem)%13]+=dp[k]
    for l in range(13):
        new_dp[l]%=MOD
    dp=new_dp
    r=(r*10)%13
print(dp[5])
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(10**7)

def cur(x):
    for i in dd[x]:
        dd[i].remove(x)
        ans[i]+=ans[x]
        cur(i)

n,q=map(int,input().split())
dd=collections.defaultdict(list)
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    dd[a].append(b)
    dd[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

cur(1)
print(*ans[1:])

### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])
### BUGGY CODE ###

from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

new_H = [h for h in range(H) if A[h + 1] == max_A]
new_W = [w for w in range(W) if B[w + 1] == max_B]

max_num = max_A + max_B - 1
for i in new_H:
    for j in new_W:
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] not in hw:
                print(max_A + max_B)
                exit()

print(max_num)


### FIXED CODE ###

H, W, M = map(int, input().split())
hw = set()
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.add((h, w))
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if (i + 1, j + 1) not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

b = set(a)
c = []
for i in b:
  x = a.count(i)
  c.append([i, x])

t = []
m = len(c)
for j in range(m):
  total = c[j][1]
  
  if c[j][0]-1 in b:
    total += c[j-1][1]
  
  if c[j][0]+1 in b:
    total += c[j+1][1]

  t.append(total)

print(max(t))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0] * (int(1e5)+5)
for i in range(n):
    ans[a[i]-1] += 1
    ans[a[i]] += 1
    ans[a[i]+1] += 1
print(max(ans))
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    temp = 0
    minimum = min(A)
    for i in range(N):
        temp = A[i]
        A[i] = minimum
        print(max(A))
        A[i] = temp


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    A_sorted = sorted(A)

    for i in range(N):
        if A_sorted[-1] == A[i]:
            print(A_sorted[-2])
        else:
            print(A_sorted[-1])


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

def main():
    a, b, x = map(int, input().split())
    mod = [i for i in range(a, b + 1) if i % x == 0]
    print(len(mod))

if __name__ == "__main__":

    main()

### FIXED CODE ###

def main():
    a, b, x = map(int, input().split())

    b_count = (b // x) + 1
    if a == 0:
        a_count = 0
    else:
        a_count = ((a - 1) // x) + 1
    print(b_count - a_count)

    # mod = [i for i in range(a, b + 1) if i % x == 0]
    # print(len(mod))

if __name__ == "__main__":

    main()
### BUGGY CODE ###

import numpy as np
s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
tem = [i%13 for i in range(130)]
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        te = tem[:t*10:t]
        pre = [np.sum([pre[(13+k-i)%13] for i in te])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5])

### FIXED CODE ###

s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]
for f in bc:
    a = [f[1] if j == f[0] else j for j in a]
    print(sum(a))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]
l = [0] * 100000
suml = 0
for i in a:
  l[i-1] += 1
  suml += i
for i in bc:
  suml += l[i[0]-1] * (i[1] - i[0])
  l[i[1]-1] += l[i[0]-1]
  l[i[0]-1] = 0
  print(suml)
### BUGGY CODE ###

# ABC 122, c
n, q = [int(el) for el in input().split(' ')]
s = input()
T = [1 if s[i:i+2] == 'AC' else 0 for i in range(n-1)]


for i in range(q):
    l, r = [int(el) for el in input().split(' ')]
    print(sum(T[(l-1):(r-1)]))


### FIXED CODE ###

# ABC 122, c
n, q = [int(el) for el in input().split(' ')]
s = input()
T = [0] * (n + 1)
for i in range(n):
    T[i+1] = T[i] + (1 if s[i:i+2] == 'AC' else 0)


for i in range(q):
    l, r = [int(el) for el in input().split(' ')]
    print(T[r-1] - T[l-1])
### BUGGY CODE ###

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

for i in range(1,len(b)+1):
    print(b.count(i))
print(0)

### FIXED CODE ###

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

c=collections.Counter(b)
n,m=zip(*c.most_common())
n,m=list(n),list(m)
o=c.most_common()

result=[0]*a
for i in range(len(o)):
    result[o[i][0]-1]=o[i][1]

for i in result:
    print(i)
### BUGGY CODE ###

import numpy as np
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    s = [list(input()) for _ in range(H)]
    s = np.array(s)
    L = np.zeros((H, W))
    R = np.zeros((H, W))
    T = np.zeros((H, W))
    B = np.zeros((H, W))
    for h in range(H):
        for w in range(W):
            cnt = 0
            for v in s[h, w:]:
                if v == "#":
                    break
                cnt += 1
            R[h, w] = cnt
    for h in range(H):
        for w in range(W):
            cnt = 0
            for v in reversed(s[h, :w + 1]):
                if v == "#":
                    break
                cnt += 1
            L[h, w] = cnt
    for h in range(H):
        for w in range(W):
            cnt = 0
            for v in s[h:, w]:
                if v == "#":
                    break
                cnt += 1
            B[h, w] = cnt
    for h in range(H):
        for w in range(W):
            cnt = 0
            for v in reversed(s[:h + 1, w]):
                if v == "#":
                    break
                cnt += 1
            T[h, w] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            res = R[h, w] + L[h, w] + B[h, w] + T[h, w] - 3
            ans = max(ans, res)
    print(int(ans))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    s = [list(input()) for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    T = [[0] * W for _ in range(H)]
    B = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if s[h][w] == "#":
                R[h][w] = 0
            elif w == 0:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w - 1] + 1
    for h in range(H):
        for w in reversed(range(W)):
            if s[h][w] == "#":
                L[h][w] = 0
            elif w == W - 1:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w + 1] + 1
    for w in range(W):
        for h in range(H):
            if s[h][w] == "#":
                B[h][w] = 0
            elif h == 0:
                B[h][w] = 1
            else:
                B[h][w] = B[h-1][w] + 1
    for w in range(W):
        for h in reversed(range(H)):
            if s[h][w] == "#":
                T[h][w] = 0
            elif h == H - 1:
                T[h][w] = 1
            else:
                T[h][w] = T[h + 1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            res = R[h][w] + L[h][w] + B[h][w] + T[h][w] - 3
            ans = max(ans, res)
    print(int(ans))


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

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def calc(x,f):#xは数字
        if x in f.keys():
            return f
        xn=x
        x=bin(x)[2:]
        cnt=sum(list(map(int,list(x))))
        if xn%cnt==0:
            f[xn]=1
            return f
        else:
            f=calc(xn%cnt,f)
            f[xn]=f[xn%cnt]+1
            return f
    
    n=int(input())    
    x=input()
    cnt=sum(list(map(int,list(x))))
    x=int(x,2)
    ans=[]
    f={}
    f[0]=0
    for i in range(n):
        if x>>i&1:
            f=calc(x-2**i,f)
            ans.append(f[x-2**i])
        else:
            f=calc(x+2**i,f)
            ans.append(f[x+2**i])
    print(*ans[::-1],sep='\n')

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]

    def popcount(n):
        c=format(n,'b').count('1')
        if c!=0:
            return n%c
        else:
            return 0
    def f(n):
        count=0
        while n>0:
            n=popcount(n)
            count+=1
        return count
        
    n=int(input())    
    x=input()
    cnt=x.count('1')
    x10=int(x,2)
    ans=[]
    a=x10%(cnt+1)
    if cnt==1:
        b=0
    else:
        b=x10%(cnt-1)
    for i in range(n):
        if x[i]=='1' and cnt==1:
            print(0)
            continue
        elif x[i]=='1':
            cal=(b-pow(2,n-1-i,cnt-1))%(cnt-1)
        else:
            cal=(a+pow(2,n-1-i,cnt+1))%(cnt+1)
        print(f(cal)+1)

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


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Nlis[0] = 0

while len(Q) > 0:

    now = Q.pop(0)

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

for i in Nlis:
    print(i)

### FIXED CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Q_cnt = 0
Nlis[0] = 0

while len(Q) > Q_cnt and N != 1:

    now = Q[Q_cnt]
    Q_cnt += 1

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            #Ndic[nw[0]].remove([now,nw[1]])

for i in Nlis:
    print(i)