codeforces#P1833G. Ksyusha and Chinchilla
Ksyusha and Chinchilla
Description
Ksyusha has a pet chinchilla, a tree on $n$ vertices and huge scissors. A tree is a connected graph without cycles. During a boring physics lesson Ksyusha thought about how to entertain her pet.
Chinchillas like to play with branches. A branch is a tree of $3$ vertices.
The branch looks like this. A cut is the removal of some (not yet cut) edge in the tree. Ksyusha has plenty of free time, so she can afford to make enough cuts so that the tree splits into branches. In other words, after several (possibly zero) cuts, each vertex must belong to exactly one branch.
Help Ksyusha choose the edges to be cut or tell that it is impossible.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — 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 next $n - 1$ rows of each testcase contain integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$) — the numbers of vertices that the $i$-th edge connects.
It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^5$.
Print the answer for each testcase.
If the desired way to cut the tree does not exist, print $-1$.
Otherwise, print an integer $k$ — the number of edges to be cut. In the next line, print $k$ different integers $e_i$ ($1 \le e_i < n$) — numbers of the edges to be cut. If $k = 0$, print an empty string instead.
If there are several solutions, you can print any.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — 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 next $n - 1$ rows of each testcase contain integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$) — the numbers of vertices that the $i$-th edge connects.
It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of $n$ over all testcases does not exceed $2 \cdot 10^5$.
Output
Print the answer for each testcase.
If the desired way to cut the tree does not exist, print $-1$.
Otherwise, print an integer $k$ — the number of edges to be cut. In the next line, print $k$ different integers $e_i$ ($1 \le e_i < n$) — numbers of the edges to be cut. If $k = 0$, print an empty string instead.
If there are several solutions, you can print any.
4
9
1 2
4 3
7 9
5 4
4 6
3 2
8 7
1 7
6
1 2
1 3
4 3
1 5
6 1
6
1 2
3 2
3 4
4 5
6 5
5
1 3
5 3
5 2
3 4
4
2
1 2
3
1 2
3 1
6
1 2
3 1
3 4
3 5
6 1
9
2 6
6 9
9 1
9 7
1 8
7 3
8 5
4 7
2
2 8
-1
1
3
-1
-1
0
1
2
2
4 3
Note
The first testcase in first test.