Same Parity Split

Ahasan_1999 CUET CSE Fest 2022 - Inte...
Limits 2s, 512 MB

A tree is a connected graph without a cycle. Given an undirected tree with nn nodes labeled from 11 to nn. Each node has a certain weight assigned to it given by an integer array AA of size nn.

Eren wants to split the tree into several different connected components by deleting KK different edges from the tree. Now, he is wondering what is the minimum value of KK such that after deleting KK different edges, the XOR value of each resulting component has the same parity.

In other words, deleting KK different edges will split the tree into K+1K+1 different connected components. Now, let’s say the XOR of each connected component is XiX_i for all (1iK+1)(1 \leq i \leq K+1). Either all XiX_i must be even or all XiX_i must be odd. The value of KK must be at least 11.

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 1-1 if it is not possible.


Each test contains multiple test cases. The first line contains a single integer TT (1T4×104)(1 ≤ T ≤ 4 \times 10^{4})— the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer nn (2n5×105)(2 ≤ n≤ 5 \times 10^{5}) — the number of vertices in the tree.

The second line contains nn space-separated integers A1,A2,,An(1Ai109)A_1,A_2,…,A_n(1≤ A_i ≤ 10^9) — the weight of the vertices.

Next n1n−1 lines contain the edges of the tree — one per line. Each line contains two integers uu and vv (1u,vn;uv)(1 ≤ u,v ≤n; u ≠ v) representing one edge of the tree. It's guaranteed that the given edges form a tree.

It is guaranteed that the sum of nn over all test cases does not exceed 5×1055 \times 10^{5}


For each test case, first, print 1-1 if it is not possible to split, otherwise, print the minimum value of KK.

If it is possible to split, print an additional line containing KK space-separated integers P1,P2,,PKP_1, P_2, …, P_K (1Pin1)( 1 \leq P_i \leq n - 1)— the index of the deleted edge. You can print the index in any order.

If there are multiple possible answers, print any of them.


1 4 2 5 3
1 2
1 4
3 2
2 5
2 1 4
1 2
2 3
1 2

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.


Login to submit.


100% Solution Ratio
Mestu_PaulEarliest, 1M ago
tanzim_bnFastest, 0.1s
tanzim_bnLightest, 37 MB
Alamin_1804084Shortest, 2140B
Toph uses cookies. By continuing you agree to our Cookie Policy.