A tree is a connected graph without a cycle. Given an undirected tree with nodes labeled from to . Each node has a certain weight assigned to it given by an integer array of size .
Eren wants to split the tree into several different connected components by deleting different edges from the tree. Now, he is wondering what is the minimum value of such that after deleting different edges, the XOR value of each resulting component has the same parity.
In other words, deleting different edges will split the tree into different connected components. Now, let’s say the XOR of each connected component is for all . Either all must be even or all must be odd. The value of must be at least .
XOR of a connected component is defined by the bitwise XOR of the weight of all the nodes in that component.
Help Eren to solve the problem or print if it is not possible.
Each test contains multiple test cases. The first line contains a single integer — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer — the number of vertices in the tree.
The second line contains space-separated integers — the weight of the vertices.
Next lines contain the edges of the tree — one per line. Each line contains two integers and representing one edge of the tree. It's guaranteed that the given edges form a tree.
It is guaranteed that the sum of over all test cases does not exceed
For each test case, first, print if it is not possible to split, otherwise, print the minimum value of .
If it is possible to split, print an additional line containing space-separated integers — the index of the deleted edge. You can print the index in any order.
If there are multiple possible answers, print any of them.
Input | Output |
---|---|
2 5 1 4 2 5 3 1 2 1 4 3 2 2 5 3 2 1 4 1 2 2 3 | 2 1 2 -1 |
In the first case, one of the possible solutions is to delete the first two edges. So, the minimum value of K is 2. In the second case, it is not possible to split the tree satisfying the condition. |