← 返回题目列表

Codeforces · 1833/G

G. 克苏莎和龙猫

中文机器翻译题面 查看原题

Ksyusha 有一只宠物龙猫、一棵位于 $$$n$$$ 顶点的树和巨大的剪刀。树是没有环的连通图。在一堂无聊的物理课上,克苏莎思考着如何取悦她的宠物。

龙猫喜欢玩树枝。分支是一棵有 $$$3$$$ 个顶点的树。

分支看起来像这样。

切割是删除树中的一些(尚未切割的)边。克苏莎有充足的空闲时间,因此她有能力进行足够的砍伐,使树分裂成树枝。换句话说,经过几次(可能是零次)切割后,每个顶点必须恰好属于一个分支。

帮助 Ksyusha 选择要切割的边缘或告知这是不可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。

每个测试用例的接下来 $$$n - 1$$$ 行包含整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) - 第 $$$i$$$ 条边连接的顶点数。

保证这组边形成一棵树。还保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

打印每个测试用例的答案。

如果所需的砍树方式不存在,则打印 $$$-1$$$。

否则,打印一个整数 $$$k$$$ — 要切割的边数。在下一行中,打印 $$$k$$$ 不同的整数 $$$e_i$$$ ($$$1 \le e_i < n$$$) — 要切割的边的编号。如果 $$$k = 0$$$,则打印空字符串。

如果有多个解决方案,您可以打印任何一个。

示例

输入 #1

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

输出 #1

2
2 8 
-1
1
3 
-1

输入 #2

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

-1
0

1
2 
2
4 3

注意

第一个测试中的第一个测试用例。