C. Colorful Tree
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

There is a tree having $$$n$$$ nodes, the $$$i$$$-th node of which has a type of color, denoted by an integer $$$c_i$$$.

The path between every two nodes is unique, of which we define the value is the number of distinct types of colors appearing on it.

Calculate the sum of values of all possible paths, $$$\frac{n (n - 1)}{2}$$$ in total, between two different nodes on the tree.

Input

The input contains multiple (about $$$50$$$) test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$), indicating the number of nodes.

The next line contains $$$n$$$ integers, the $$$i$$$-th number of which is $$$c_i$$$ ($$$1 \leq c_i \leq n$$$), denoting the color of the $$$i$$$-th node.

Each of the next $$$(n - 1)$$$ lines contains two integers $$$x$$$, $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x \neq y$$$), representing an edge between the $$$x$$$-th node and the $$$y$$$-th one. It is guaranteed that given edges form a tree.

Output

For each test case, output "Case #x: y" in one line (without quotes), where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ denotes the answer to the corresponding case.

Example
Input
3
1 2 1
1 2
2 3
6
1 2 1 3 2 1
1 2
1 3
2 4
2 5
3 6
Output
Case #1: 6
Case #2: 29