A. Yet Another Colored Tree Problem
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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
Input
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
Output
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$$$.