Codeforces Round 874 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

dfs and similar

dp

dsu

greedy

implementation

trees

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Ksyusha and Chinchilla

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKsyusha 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.

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 $$$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.

Examples

Input

491 24 37 95 44 63 28 71 761 21 34 31 56 161 23 23 44 56 551 35 35 23 4

Output

2 2 8 -1 1 3 -1

Input

421 231 23 161 23 13 43 56 192 66 99 19 71 87 38 54 7

Output

-1 0 1 2 2 4 3

Note

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:59:28 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|