# Ksyusha and Chinchilla solution codeforces

## Ksyusha and Chinchilla solution codeforces

Ksyusha has a pet chinchilla, a tree on 𝑛 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 branchesA branch is a tree of 33 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

The first line contains a single integer 𝑡 (1𝑡1041≤�≤104) — number of testcases.

The first line of each testcase contains a single integer 𝑛 (2𝑛21052≤�≤2⋅105) — the number of vertices in the tree.

The next 𝑛1�−1 rows of each testcase contain integers 𝑣𝑖�� and 𝑢𝑖�� (1𝑣𝑖,𝑢𝑖𝑛1≤��,��≤�) — the numbers of vertices that the 𝑖-th edge connects.

It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of 𝑛 over all testcases does not exceed 21052⋅105.

Output

Print the answer for each testcase.

If the desired way to cut the tree does not exist, print 1−1.

Otherwise, print an integer 𝑘 — the number of edges to be cut. In the next line, print 𝑘 different integers 𝑒𝑖�� (1𝑒𝑖<𝑛1≤��<�) — numbers of the edges to be cut. If 𝑘=0�=0, print an empty string instead.

If there are several solutions, you can print any.

Examples
input

Copy
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

## Ksyusha and Chinchilla solution codeforces

Copy
2
2 8
-1
1
3
-1

input

Copy
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
output

Copy
-1
0

1
2
2
4 3

Note

The first testcase in first test.