I. Buzău
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little IR12660 is gone meeting with a friend flying in from Nice. He has a lot of catching up to do over a good cup of joe and pretzels, so he is unavailable to solve the following problem. Please, do it in his stead:

You are given a tree with $$$N$$$ ($$$1 \le N \le 100\,000$$$) nodes and $$$N - 1$$$ edges. Each node is attributed a color, which we will conveniently label with numbers from $$$1$$$ to $$$K$$$ ($$$1 \le K \le N$$$). We define a chain as a set of nodes that lie on the minimum length path between two nodes. We call these two nodes the endpoints of the chain. Then, we define a correct chain arrangement as a set of chains such that:

  • For every chain, the endpoints of it have the same color,
  • For every color $$$c$$$ ($$$1 \le c \le K$$$) there is exactly one chain such that the color of its endpoints is $$$c$$$.

For such a correct chain arrangement, let it be called $$$A$$$, we define $$$d_u$$$ as the number of chains in $$$A$$$ of which node $$$u$$$ is part of. More formally, $$$d_u = card(\{ C \,\,\, | \,\, C \subset A, u \in C \})$$$, where $$$card(S)$$$ denotes the number of elements in that set.

Determine the lexicographically maximal array $$$A_V = [d_1, d_2, .. , d_N]$$$ such that there exists a correct chain arrangement $$$A$$$ that yields it.

Input

You are given $$$K$$$ ($$$1 \le K \le N$$$) and $$$N$$$ ($$$1 \le N \le 100\,000$$$).

On the next line, you are given $$$N$$$ numbers, the $$$i$$$-th of which denotes $$$c_i$$$ ($$$1 \le c_i \le N$$$), the color of the i-th node. Within the tests used, every color has at least one node that contains it.

Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N, u \neq v$$$), meaning that there is an edge between $$$u$$$ and $$$v$$$ in the tree.

Output

Print $$$N$$$ numbers, forming the lexicographically maximal array that could be generated by a correct chain arrangement

Example
Input
3 7
1 1 3 2 2 1 2
5 1
5 3
1 4
1 7
3 6
3 2
Output
2 1 2 1 2 0 0
Note

The chains used in the first example are as follows:

  • For color 1, the chain with endpoints in 1 and 2
  • For color 2, the chain with endpoints in 4 and 5
  • For color 3, the chain containing only node 3