Ksyusha and Chinchilla
Contest: Codeforces Round 874 (Div. 3)
Difficulty rating: 1800
Tags: constructive algorithms, dfs and similar, dp, dsu, greedy, implementation, trees

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.

Input format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The first testcase in first test.

Example input:
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

Example output:
2
2 8 
-1
1
3 
-1

Example input:
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

Example output:
-1
0

1
2 
2
4 3

Editorial:
Let's hang the tree by the vertex $$$1$$$. This problem can be solved by dynamic programming.
1. $$$dpc_v$$$ — the ability to cut a subtree of $$$v$$$ if the edges in all children of $$$v$$$ must be cut off.
2. $$$dpo_v$$$ — the ability to cut a subtree of $$$v$$$ if exactly one edge needs to be saved from $$$v$$$ to the child.
3. $$$dp_v$$$ — ability to cut a subtree of $$$v$$$ if an edge above $$$v$$$ is cut off.
Obviously, the answer will be $$$dp_1$$$. Recalculation in such dynamics is offered to the reader as an exercise.
There is a simpler greedy solution. Let's call light a vertex that is not a leaf and whose children are all leaves. Let's call heavy a vertex that is not a leaf and that has a light child.
If there is a light vertex with at least three children, the desired cut does not exist. If the light vertex $$$v$$$ has exactly one child, we will cut off all children from its parent except $$$v$$$. If the light vertex $$$v$$$ has exactly two children, we cut the edge into the parent $$$v$$$.
It is easy to understand that in this way the desired cut is restored uniquely. This problem can be solved by an elegant DFS, but the author considers BFS easier to understand.
First, let's count the number of children and the number of light children for each vertex. We will store all light vertices in the queue and process them sequentially. Cutting edges will change the number of children and the number of light children at some vertices. It should be handled carefully.
This solution works for $$$O(n)$$$.