You are given a tree with $n$ nodes. Each node has a color between $1$ and $k$.

For each color $i$ from $1$ to $k$, print the number of simple paths that contain at least one node with color $i$.

A simple path is a sequence of edges $(u_1,u_2),(u_2,u_3),\ldots,(u_{k-1},u_k)$ for which all $u_i$ are pairwise distinct. Two paths are considered different if their corresponding sequences of edges are distinct.

Input

Each test contains multiple testcases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) — the number of nodes and colors, respectively.

The second line contains $n$ integers $c_1,c_2,\ldots,c_n$ ($1 \le c_i \le k$) — the colors of the $n$ nodes.

Each of the next $n-1$ lines contain two integers $u_i$ and $v_i$ ($1 \le u_i,v_i \le n$, $u_i \neq v_i$), meaning that an undirected edge exists between nodes $u_i$ and $v_i$.

It is guaranteed that the given graph is a tree (an undirected connected graph without cycles).

It is also guaranteed that the sum of $n$ across all testcases does not exceed $3 \cdot 10^5$.

Output

For each testcase, print $k$ integers, the number of simple paths that contain at least one node with color $i$, for every color $i$ from $1$ to $k$.

Example

stdin

4
3 3
1 1 3
1 2
1 3
1 1
1
5 3
1 2 3 2 1
1 2
1 3
3 4
3 5
8 7
1 1 2 3 5 6 7 2
1 2
1 3
1 4
2 5
2 6
3 7
5 8

stdout

8 0 5
1
20 16 19
54 38 15 0 27 15 15

Note

Explanation of the first testcase:

There are $8$ simple paths that contain at least one node with color $1$:

• $[1]$
• $[2]$
• $[1 \rightarrow 2]$
• $[2 \rightarrow 1]$
• $[1 \rightarrow 3]$
• $[3 \rightarrow 1]$
• $[2 \rightarrow 1 \rightarrow 3]$
• $[3 \rightarrow 1 \rightarrow 2]$

Since there are no nodes with color $2$, there are no paths that contain a node with color $2$.

Finally, there are $5$ simple paths that contain at least one node with color $3$:

• $[3]$
• $[3 \rightarrow 1]$
• $[1 \rightarrow 3]$
• $[3 \rightarrow 1 \rightarrow 2]$
• $[2 \rightarrow 1 \rightarrow 3]$

In the second testcase, the only path ($[1]$) contains one node with color $1$.