Statement : F. MEX Replacement on Tree

You are given a tree rooted at $1$ with $n$ vertices and a permutation $p$ of length $n$ consisting of integers $0, 1, \ldots, n - 1$, where $p_v$ represents the weight of vertex $v$.

Let $S_v$ denote the set of weights written on the vertices belonging to the path from $1$ to $v$. Define a function $f$ as $f(v) = \mathrm{MEX}(S_v)$, that is, the $\mathrm{MEX}$ over the set consisting of the weights of vertices on the simple path between the root and $v$ (inclusive), where $\operatorname{MEX}$ of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.

Also, given the following operation:

• Choose an integer $v$ ($1 \leq v \leq n$) and assign $f(v)$ to $p_v$.

Your goal is to find the maximum value of $\sum\limits_{v = 1}^n f(v)$ after performing the above operation no more than once (possibly zero).

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of vertices of the tree.

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($0 \le p_i \le n - 1$) — the elements of array $p$. It is guaranteed that every integer from $0$ to $n - 1$ appears exactly once in $p$.

Then $n - 1$ lines follow, each line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), indicating an edge between vertices $x_i$ and $y_i$. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output a single line containing an integer: the maximum value of $\sum\limits_{v = 1}^n f(v)$ after performing the above operation no more than once (possibly zero).

Input

7
1
0
3
1 0 2
1 2
1 3
6
1 4 5 2 0 3
1 4
1 5
6 2
2 5
2 3
5
1 2 3 0 4
1 2
2 3
3 4
4 5
10
9 8 7 1 3 2 5 4 6 0
6 10
3 1
8 7
4 2
2 8
7 5
10 9
3 9
6 4
9
8 4 0 6 5 7 3 1 2
8 3
4 2
4 6
9 3
7 6
1 5
8 5
9 2
7
1 5 2 3 6 0 4
7 6
4 3
7 2
5 1
2 4
6 5

Output

1
4
12
9
30
26
17

Note

In the first example, not doing any operation is optimal, so the answer is $1$.

In the second example, we have

• $f(1) = \mathrm{MEX}(\{p_1\}) = \mathrm{MEX}(\{1\}) = 0$
• $f(2) = \mathrm{MEX}(\{p_1, p_2\}) = \mathrm{MEX}(\{1, 0\}) = 2$
• $f(3) = \mathrm{MEX}(\{p_1, p_3\}) = \mathrm{MEX}(\{1, 2\}) = 0$

And we have the following options:

• Doing nothing would lead to $\sum\limits_{v = 1}^n f(v) = 2$
• Doing operation on vertex $1$ would assign $f(1) = 0$ to $p_1$, change $f(1), f(2), f(3)$ to $1$, which leads to $\sum\limits_{v = 1}^n f(v) = 3$
• Doing operation on vertex $2$ would assign $f(2) = 2$ to $p_2$, change $f(2)$ to $0$, which leads to $\sum\limits_{v = 1}^n f(v) = 0$
• Doing operation on vertex $3$ would assign $f(3) = 0$ to $p_3$, change $f(3)$ to $2$, which leads to $\sum\limits_{v = 1}^n f(v) = 4$

So the answer is $4$, by doing operation on vertex $3$.