You are given an undirected tree of even number of nodes $n$. Each node has a color, and no more than two nodes have the same color. Nodes are numbered from $1$ to $n$. Colors are numbered from $1$ to $\frac{n}{2}$.

Your task is to find the length of the longest path in the tree that contains only distinct colors. The length of a path is the number of edges we traverse from source to destination.

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

The first line of each test case contains a single even integer $n$ ($2 \leq n \leq 5\times10^4$), the number of nodes in the tree.

The second line contains $n$ integers $c_1$, $c_2$, $\dots$, $c_n$ ($1 \leq c_i \leq \frac{n}{2}$), where $c_i$ is the color of the $i^{th}$ node.

It is guaranteed that no more than two nodes will have the same color.

Each of the following $n-1$ lines will contain two integers $u$ and $v$ ($1 \leq u,v \leq n$), representing an edge between the two nodes $u$ and $v$. It is guaranteed that the given graph is a tree.

The total sum of $n$ over all test cases doesn't exceed $5\times10^5$.

For each test case, print a single line with the length of the longest path in the tree that contains only distinct colors.