Longest Even-Valued Path in a Tree

You are given a tree with N nodes. Each node is assigned an integer value. Your task is to determine the length of the longest path (in terms of the number of edges) in the tree such that every node on this path has an even value.

The tree is defined by N nodes and N-1 undirected edges. A path is a sequence of nodes where each consecutive pair is connected by an edge. The length of a path is equal to the number of edges in that path.

More formally, let \( V = \{v_1, v_2, \dots, v_N\} \) be the set of node values and let the tree be represented by a set of edges \( E \). Find the maximum integer \( L \) such that there exists a sequence of nodes \( (a_1, a_2, \dots, a_{L+1}) \) satisfying:

• For each \( 1 \leq i \leq L \), the edge \( (a_i, a_{i+1}) \) is in \( E \),
• Each node in the sequence has an even value, i.e. \( v_{a_i} \) is even for all \( i \).

If no such path exists, output 0.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
N
v1 v2 ... vN
u1 v1
u2 v2
... (N-1 lines of edges)
[Next test case if T > 1]

Where:

• T is the number of test cases.
• For each test case, N is the number of nodes in the tree.
• The next line contains N integers representing the values of the nodes.
• The following N-1 lines each contain two integers representing an edge connecting two nodes.

outputFormat

For each test case, output a single integer on a new line through standard output (stdout) — the length (number of edges) of the longest path in the tree such that every node in the path has an even value. If no such path exists, output 0.

## sample

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

4
0

</p>