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
注意
第一个测试中的第一个测试用例。