A. K-Color Union
time limit per test
10 с
memory limit per test
256 megabytes
input
standard input
output
standard output

The city of Chromatica has $$$N$$$ landmarks connected by $$$N-1$$$ bidirectional roads forming a tree structure. Each landmark is painted with one of $$$K$$$ distinct colors (numbered $$$1$$$ to $$$K$$$).

The city's tourism board wants to promote "rainbow tours" — tours that visit all $$$K$$$ colors at least once. A tour is defined as starting at one landmark and ending at another, following the unique path between them.

To design their marketing campaign, they need to know: how many distinct pairs of landmarks can form a rainbow tour?

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10$$$), the number of test cases. The description of $$$T$$$ test cases follows.

Each test case is described as follows:

  • The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le 10$$$).
  • The second line contains $$$N$$$ integers $$$c_1, c_2, \dots, c_N$$$ ($$$1 \le c_i \le K$$$), where $$$c_i$$$ is the color of the $$$i$$$-th landmark.
  • Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$, $$$u \neq v$$$), describing an undirected road between landmark $$$u$$$ and landmark $$$v$$$.

It is guaranteed that the roads form a tree, and the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer — the number of unordered pairs $$$(u, v)$$$ such that the path from $$$u$$$ to $$$v$$$ contains at least one landmark of each of the $$$K$$$ colors.

Example
Input
2
4 3
1 2 3 2
1 2
2 3
3 4
5 3
1 1 2 3 2
1 2
2 3
3 4
4 5
Output
2
4