在玩把两棵树拼成一个图的游戏。他用两棵 个点的树拼成了一个 个点、 条边的无向无权图 。但是他发现他没法把这个图还原回两棵树了,请你帮帮他!
形式化地说,请你将所有边恰好分成两个集合 和 ,使得 和 都构成 的一棵生成树。
你可以输出任意一种合法方案。保证合法方案一定存在。
注意:图中可能存在重边,但保证不存在自环。
第一行有一个整数 (),表示数据组数。接下来 段,每段描述一组数据:
数据保证 不超过 。
对于每组数据,输出 个整数(升序),表示第一棵生成树包含的边的编号。剩余的 条边也应构成一棵生成树。
2 3 1 2 2 3 1 3 1 2 4 1 2 2 3 3 4 1 4 1 3 2 4
1 2 1 2 3
对于第一组样例,边 对应 ,构成一棵生成树。剩余边 对应 ,也构成一棵生成树。
对于第二组样例,边 对应 ,构成一棵生成树。剩余边 对应 ,也构成一棵生成树。