CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  _, m = list(map(int, input().split()))
  traps = [v == '1' for v in input().strip()]
  values = [None] * len(traps)
  values[0] = -1

  for i in range(len(values) - 1):
    if values[i] is None:
      continue

    for j in range(i + m, i, -1):
      if j >= len(values) or traps[j]:
        continue

      if values[j] is not None:
        break

      values[j] = i

  if values[-1] is None:
    print((-1))
    return

  index = len(values) - 1
  route = []

  while values[index] != -1:
    route.append(index - values[index])
    index = values[index]

  print((' '.join(str(v) for v in route[::-1])))


if __name__ == '__main__':
  main()


# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  _, m = list(map(int, input().split()))
  traps = [v == '1' for v in input().strip()]
  values = [None] * len(traps)
  values[0] = -1

  for i in range(len(values) - 1):
    if values[i] is None:
      continue

    for j in range(min(i + m, len(values) - 1), i, -1):
      if j >= len(values) or traps[j]:
        continue

      if values[j] is not None:
        break

      values[j] = i

  if values[-1] is None:
    print((-1))
    return

  index = len(values) - 1
  route = []

  while values[index] != -1:
    route.append(index - values[index])
    index = values[index]

  print((' '.join(str(v) for v in route[::-1])))


if __name__ == '__main__':
  main()
# Original solution
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, M = mis()
    S = input()

    @lru_cache(maxsize=None)
    def rec(n):
        if n < 0 or S[n] == '1':
            return None, INF
        elif n == 0:
            return None, 0
        min_i = None
        min_v = INF
        for i in range(max(n-M, 0), n):
            _, v = rec(i)
            if min_v > v:
                min_v = v
                min_i = i
        return min_i, min_v

    flag, _ = rec(N)
    if flag is None:
        print(-1)
    else:
        ans = []
        pos = N
        while pos != 0:
            prev_pos, _ = rec(pos)
            ans.append(pos - prev_pos)
            pos = prev_pos
        ans.reverse()
        print(*ans, sep=' ')



main()


# Optimized solution
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, M = mis()
    S = input()

    ans = []
    r = N
    l = max(r - M, 0)
    while r > 0:
        for i in range(l, r):
            if S[i] == '0':
                ans.append(r - i)
                r = i
                l = max(r - M, 0)
                break
        else:
            print(-1)
            return
    ans.reverse()
    print(*ans, sep=' ')


main()
# Original solution
# -*- coding: utf-8 -*-
import sys

N,M=list(map(int, sys.stdin.readline().split()))
S=sys.stdin.readline().strip()

L=[]    #答えの集合
for _ in range(N):
    for m in range(M,0,-1):
        if 0<=N-m and S[N-m]=="0":
            L.append(m)
            N-=m
            break
    else:
        break
        
if N!=0:
    print(-1)
else:
    print(" ".join(map(str,L[::-1])))


# Optimized solution
# -*- coding: utf-8 -*-
import sys

N,M=list(map(int, sys.stdin.readline().split()))
S=sys.stdin.readline().strip()

L=[]    #答えの配列の逆順
for _ in range(N):
    for m in range(M,0,-1):
        if 0<=N-m and S[N-m]=="0":
            L.append(m)
            N-=m
            break
    else:
        break
        
if N!=0:
    print(-1)
else:
    print(" ".join(map(str,L[::-1])))
# Original solution
from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = list(map(int, input().split()))
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [[] for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = dp2[idx] + [i-idx]
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print((-1))
else:
    print((" ".join(map(str, dp2[-1]))))


# Optimized solution
from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = list(map(int, input().split()))
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [-1 for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = idx
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print((-1))
else:
    r = []
    s = N
    while True:
        if s == 0:
            break
        ns = dp2[s]
        r.append(s-ns)
        s = ns
    print((" ".join(map(str, r[::-1]))))
# Original solution
from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = list(map(int, input().split()))
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [-1 for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = idx
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print((-1))
else:
    r = []
    s = N
    while True:
        if s == 0:
            break
        ns = dp2[s]
        r.append(s-ns)
        s = ns
    print((" ".join(map(str, r[::-1]))))


# Optimized solution
N,M=map(int,input().split())
S,r,s=input(),[],N
for _ in range(2*N):
    if S[s]=='1':
        s += 1
    else:
        r.append(str(N-s))
        N,s=s,max(0,s-M)
    if N == 0:
        break
print(*[-1] if s else r[1:][::-1])
# Original solution
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, S: str):

    # 最短手数を求める
    DP = [INF]*(N+1)
    DP[0] = 0
    for i in range(1, N+1):
        if S[i] == "1":
            continue
        for j in range(1, M+1):
            if i-j < 0:
                break
            DP[i] = min(DP[i], DP[i-j]+1)

    if DP[-1] == INF:
        print(-1)
        return
    # 逆順に辿って実際の手を求める
    # 辞書順になるよう、後ろから貪欲に選ぶ
    ans = []
    curr = N
    while curr > 0:
        for i in range(M, 0, -1):
            if curr-i < 0:
                continue
            if curr-i == 0:
                break
            if DP[curr-i] < DP[curr]:
                break
        curr = curr - i
        ans.append(i)
    print(*reversed(ans), sep=" ")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, M, S)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, S: str):

    S = S[::-1]
    data = [0]*(N+1)
    past = 0
    for i in range(N+1):
        if S[i] == "1":
            data[i] = past
        else:
            past = i
    ans = []
    curr = 0
    while True:
        ne = curr+M
        if ne >= N:
            ans.append(N-curr)
            break
        if S[ne] == "1":
            ne = data[ne]
            if ne <= curr:
                print(-1)
                return
        ans.append(ne - curr)
        curr = ne
    print(*reversed(ans), sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, M, S)


if __name__ == '__main__':
    main()
# Original solution
n, m = map(int, input().split())
s = input()
s = s[::-1]
if s[0] == "1":
    print(-1)
    exit()
pre = [-1] * (n + 1)
stack = [0]
while stack:
    now = stack.pop()
    if now == n:
        break
    for i in range(1, m + 1):
        tsugi = now + i
        if tsugi > n:
            continue
        if s[tsugi] == "1":
            continue
        pre[tsugi] = now
        stack.append(tsugi)
else:
    print(-1)
    exit()
ato = n
mae = pre[n]
ans = []
while mae >= 0:
    ans.append(ato - mae)
    ato = mae
    mae = pre[ato]
print(*ans, sep=" ")


# Optimized solution
n, m = map(int, input().split())
s = input()
out_s='1'*(m)
if out_s in s:
    print(-1)
    exit()
s = s[::-1]
if s[0] == "1":
    print(-1)
    exit()
pre = [-1] * (n + 1)
stack = [0]
while stack:
    now = stack.pop()
    if now == n:
        break
    for i in range(1, m + 1):
        tsugi = now + i
        if tsugi > n:
            continue
        if s[tsugi] == "1":
            continue
        pre[tsugi] = now
        stack.append(tsugi)
else:
    print(-1)
    exit()
ato = n
mae = pre[n]
ans = []
while mae >= 0:
    ans.append(ato - mae)
    ato = mae
    mae = pre[ato]
print(*ans, sep=" ")
# Original solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S = LS2()
if S[-1] == 's':
    S += ['e','s']
else:
    S += ['s']

print((''.join(S)))


# Optimized solution
import sys
def S(): return sys.stdin.readline().rstrip()


S = S()
print((S+'es' if S[-1] == 's' else S+'s'))
# Original solution
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    s = iss()
    print((s + 'es' if s[-1] == 's' else s + 's'))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


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


MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    if S[-1] == 's':
        print((S + 'es'))
    else:
        print((S + 's'))


if __name__ == '__main__':
    main()
# Original solution
temp = list(input().split())
print(((temp[0][0]+temp[1][0]+temp[2][0]).upper()))

# Optimized solution
a, b, c = input().split()
print(((a[0]+b[0]+c[0]).upper()))
# Original solution
s = list(input().split())
print(((s[0][0] + s[1][0] + s[2][0]).upper()))

# Optimized solution
s = list(input().split())
#print((s[0][0] + s[1][0] + s[2][0]).upper())
print((''.join([x[0].upper() for x in s])))
# Original solution
a,b,c=input().split()
print((a[0].upper()+b[0].upper()+c[0].upper()))

# Optimized solution
a,b,c=input().split()
print(((a[0]+b[0]+c[0]).upper()))
# Original solution
a,b,c = input().split()
ans = a[0]+b[0]+c[0]
print((ans.upper()))

# Optimized solution
a,b,c = input().split()
print(((a[0] + b[0] + c[0]).upper()))
# Original solution
s1,s2,s3=list(map(str,input().upper().split())) #文字列
print((s1[0]+s2[0]+s3[0]))

# Optimized solution
s1,s2,s3=input().upper().split() #文字列
print((s1[0]+s2[0]+s3[0]))
# Original solution
s1,s2,s3 = input().split()

print(((s1[0]+s2[0]+s3[0]).upper()))

# Optimized solution
a,b,c=input().upper().split();print((a[0]+b[0]+c[0]))
# Original solution
s1,s2,s3 = list(map(str,input().split()))

s = s1[0] + s2[0] + s3[0]

s = s.upper()

print(s)

# Optimized solution
a,b,c = input().split()
print(((a[0]+b[0]+c[0]).upper()))
# Original solution
s1,s2,s3 = input().strip().split()
print((s1[0].upper()+s2[0].upper()+s3[0].upper()))

# Optimized solution
s1,s2,s3 = input().split()
s1 = s1.upper()
s2 = s2.upper()
s3 = s3.upper()
print((s1[0]+s2[0]+s3[0]))
# Original solution
a,b,c=input().upper().split();print((''.join([a[0],b[0],c[0]])))

# Optimized solution
a,*_=zip(*input().upper().split());print(*a,sep='')
# Original solution
a,b,c = list(map(str,input().split()))
A = list(a)[0].upper()
B = list(b)[0].upper()
C = list(c)[0].upper()
print((A+B+C))


# Optimized solution
s = input().split()
for i in range(3):
    print(s[i][0].upper(), end = "")
print()
# Original solution
s = input().split()
print(''.join([w[0] for w in s]).upper())


# Optimized solution
print(''.join([w[0] for w in input().split()]).upper())
# Original solution
def main():
    S_1 , S_2 , S_3 = list(map(str, input().split(' ')))
    print((S_1[0].upper() + S_2[0].upper() + S_3[0].upper()))
    

if __name__ == '__main__':
    main()


# Optimized solution

if __name__ == "__main__":
    S = input().split()
    print(((S[0][0] + S[1][0] + S[2][0]).upper()))
# Original solution
import bisect

INF = 10 ** 10

N = int(input())
As = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(N-1)]

dfs_stack = [1]
ans = [-1] * N
lis = [INF] * (N+1)
rewinder = []

while dfs_stack:
    pos = dfs_stack.pop()
    for u, v in edges:
        if u == pos:
            if ans[v-1] == -1:
                dfs_stack.append(v)
            else:
                parent = v
        elif v == pos:
            if ans[u-1] == -1:
                dfs_stack.append(u)
            else:
                parent = u
    
    while rewinder:
        i, before, after = rewinder.pop()
        if after == As[parent-1]:
            rewinder.append( (i, before, after) )
            break
        else:
            lis[i] = before

    index = bisect.bisect_left(lis, As[pos-1])
    rewinder.append( (index, lis[index], As[pos-1]) )
    lis[index] = As[pos-1]
    ans[pos-1] = lis.index(INF)

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


# Optimized solution
from bisect import bisect_left

INF = 10 ** 9

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

adj = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)

ans = [0] * N
LIS = [INF] * (N+1)
rewinder = []

parent = [-1] * N
stack = [0]
while stack:
    node = stack.pop()
    for next_node in adj[node]:
        if ans[next_node] == 0:
            parent[next_node] = node
            stack.append(next_node)

    while rewinder and rewinder[-1][0] != parent[node]:
        _, index, prev_value = rewinder.pop()
        LIS[index] = prev_value
    
    index = bisect_left(LIS, As[node])
    rewinder.append((node, index, LIS[index]))
    LIS[index] = As[node]

    ans[node] = bisect_left(LIS, INF)

print(*ans, sep = '\n')
# Original solution
n=int(eval(input()))
l=[0]+list(map(int,input().split()))
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=list(map(int,input().split()))
    edge[a].append(b)
    edge[b].append(a)
s=1
ans=[0 for i in range(n+1)]

from bisect import bisect_left, bisect_right
INF=float('inf')

import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    cc=c[:]
    cc[bisect_left(cc,l[s])]=l[s]
    ans[s]=bisect_left(cc,INF)
    for i in edge[s]:
        if dep[i]==-1:
            dfs(i,d+1,cc)
c=[INF]*len(l)
dfs(1,0,c)
for i in range(1,n+1):
    print((ans[i]))

# Optimized solution
n=int(eval(input()))
l=[0]+list(map(int,input().split()))
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=list(map(int,input().split()))
    edge[a].append(b)
    edge[b].append(a)
s=1
ans=[0 for i in range(n+1)]

from bisect import bisect_left, bisect_right
INF=float('inf')

import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    x=bisect_left(c,l[s])
    c[x],y=l[s],c[x]
    ans[s]=bisect_left(c,INF)
    for i in edge[s]:
        if dep[i]==-1:
            dfs(i,d+1,c)
    c[x]=y
c=[INF]*len(l)
dfs(1,0,c)
for i in range(1,n+1):
    print((ans[i]))
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
a = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
L = [a[0]]
que.append((0,1,L))
chk = [False]*n
chk[0] = True
cnt = 1
ans = [1]*n
while que:
  now,m,L = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      ind = bisect_left(L,a[i])
      if m == ind:
        newm = m+1
        newL = L+[a[i]]
      else:
        newm = m
        newL = L[:ind]+[a[i]]+L[ind+1:]
      ans[i] = newm
      chk[i] = True
      cnt += 1
      que.append((i,newm,newL))

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


# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
A = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
inf = 10**9+1
dp = [inf]*n
que.append((0,-1))
chk = [False]*n
chk[0] = True
cnt = 0
ans = [1]*n

while que:
  now,d = que.pop()
  if d != -1:
    dp[now] = d
  else:
    ind = bisect_left(dp,A[now])
    que.append((ind,dp[ind]))
    dp[ind] = A[now]
    ans[now] = bisect_left(dp,inf)
    cnt += 1
    for i in g[now]:
      if not chk[i]:
        chk[i] = True
        que.append((i,-1))
  if cnt == n:
    break
        
print(*ans,sep='\n')
# Original solution
import sys
from collections import deque
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N = int(eval(input()))
    A = inpl()
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = inpl()
        edges[u].append(v)
        edges[v].append(u)
    DPs = [None] * (N + 1)
    DPs[0] = []

    Q = deque()
    Q.append(1)
    parent = [-1] * (N + 1)
    parent[1] = 0
    while Q:
        nv = Q.popleft()
        DPs[nv] = DPs[parent[nv]].copy()
        t = bisect(DPs[nv], A[nv - 1])
        if t >= len(DPs[nv]):
            DPs[nv].append(A[nv - 1])
        else:
            DPs[nv][t] = A[nv - 1]

        for kouho in edges[nv]:
            if parent[kouho] == -1:
                Q.append(kouho)
                parent[kouho] = nv

    for i in range(1, N + 1):
        print((len(DPs[i])))
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


class solve:
    def __init__(self, N):
        self.ans = [0] * N
        self.DP = []

    def recur(self, i, pi=-1):
        # DPテーブルを更新し、答えを求める。
        # また、巻き戻す値を覚える。
        rev_i = bisect(self.DP, self.A[i])
        if rev_i == len(self.DP):
            self.DP.append(self.A[i])
            rev_v = None
        else:
            rev_v = self.DP[rev_i]
            self.DP[rev_i] = self.A[i]

        self.ans[i] = len(self.DP)

        for nv in self.edges[i]:
            if nv != pi:
                self.recur(nv, i)

        # 巻き戻す。.
        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


def main():
    N = int(input())
    S = solve(N)
    S.A = inpl()
    S.edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = inpl()
        S.edges[u - 1].append(v - 1)
        S.edges[v - 1].append(u - 1)

    S.recur(0)

    print(*S.ans, sep='\n')
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()