logo AlgoBeat OnlineJudge
登录 注册

#216896. [JLCPC 2026] 拆分树

内存限制:1024 MiB 时间限制:8000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

在玩把两棵树拼成一个图的游戏。他用两棵 个点的树拼成了一个 个点、 条边的无向无权图 。但是他发现他没法把这个图还原回两棵树了,请你帮帮他!

形式化地说,请你将所有边恰好分成两个集合 ,使得 都构成 的一棵生成树。

你可以输出任意一种合法方案。保证合法方案一定存在。

注意:图中可能存在重边,但保证不存在自环。

输入格式

第一行有一个整数 ),表示数据组数。接下来 段,每段描述一组数据:

  • 第一行一个整数 ),表示点数。
  • 接下来 行,每行两个整数 ),表示一条边。边按输入顺序从 编号。

数据保证 不超过

输出格式

对于每组数据,输出 个整数(升序),表示第一棵生成树包含的边的编号。剩余的 条边也应构成一棵生成树。

样例

样例输入 1

2
3
1 2
2 3
1 3
1 2
4
1 2
2 3
3 4
1 4
1 3
2 4

样例输出 1

1 2
1 2 3

数据范围与提示

对于第一组样例,边 对应 ,构成一棵生成树。剩余边 对应 ,也构成一棵生成树。

对于第二组样例,边 对应 ,构成一棵生成树。剩余边 对应 ,也构成一棵生成树。