E. Tareq-utiful Tree
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Tareq is not just known for his technique "The Blender of Standards", he is also known for his famous sentence: "I'll be back after I heat the water jug", where he won't be back until at least 2 months later. so he proposed this problem and said his famous sentence and the other judges had to actually prepare the problem for the contest

We define a colored tree to be a Tareq-utiful Tree if it can be split into two trees, and both trees have the same multiset of colors. In other words, the frequency of each color $$$c$$$ $$$(1 \le c \le N)$$$ is equal in both formed trees.

Splitting a tree into two trees is equivalent to choosing an edge and removing it from the tree.

Given a tree of $$$N$$$ vertices, where each vertex has a color $$$C_i$$$. In one operation, you can:

  • choose any two vertices $$$u$$$ and $$$v$$$ and exchange their colors, i.e. swap$$$(C_u, C_v)$$$.

Find the minimum number of operations you need to do, so that the tree becomes a Tareq-utiful Tree, Or report that it's impossible.

Input

The first line of the input contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ $$$(2 \le N \le 2\cdot 10^5)$$$ — The number of vertices in the tree.

The second line of each testcase contains $$$N$$$ space-separated integers $$$C_1, C_2, \dots, C_N$$$ $$$(1 \le C_i \le N)$$$ — the colors of the vertices.

The next $$$N - 1$$$ lines contain the edges of the tree. Each line contains two integers $$$U$$$ and $$$V$$$ denoting an edge between vertices $$$U$$$ and $$$V$$$ $$$(1 \le U , V \le N , U \ne V)$$$. It is guaranteed that these edges form a tree.

It's guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2\cdot 10^5$$$

Output

For each testcase print a single integer representing the minimum number of operations needed to make a Tareq-utiful Tree, or $$$-1$$$ if it is impossible.

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