P16921 [JLCPC 2026] 拆分树

$\mathit{tarjen}$ 在玩把两棵树拼成一个图的游戏。他用两棵 $n$ 个点的树拼成了一个 $n$ 个点、$m = 2n - 2$ 条边的无向无权图 $G = (V, E)$。但是他发现他没法把这个图还原回两棵树了，请你帮帮他！ 形式化地说，请你将所有边恰好分成两个集合 $T$ 和 $E \setminus T$，使得 $T$ 和 $E \setminus T$ 都构成 $G$ 的一棵生成树。 你可以输出任意一种合法方案。保证合法方案一定存在。 注意：图中可能存在重边，但保证不存在自环。

第一行有一个整数 $T$（$1 \le T \le 5000$），表示数据组数。接下来 $T$ 段，每段描述一组数据： - 第一行一个整数 $n$（$2 \le n \le 5000$），表示点数。 - 接下来 $2n - 2$ 行，每行两个整数 $u, v$（$1 \le u, v \le n$，$u \ne v$），表示一条边。边按输入顺序从 $1$ 到 $2n - 2$ 编号。 数据保证 $\sum n$ 不超过 $10000$。

对于每组数据，输出 $n - 1$ 个整数（升序），表示第一棵生成树包含的边的编号。剩余的 $n - 1$ 条边也应构成一棵生成树。

对于第一组样例，边 $\{1, 2\}$ 对应 $\{(1,2), (2,3)\}$，构成一棵生成树。剩余边 $\{3, 4\}$ 对应 $\{(1,3), (1,2)\}$，也构成一棵生成树。 对于第二组样例，边 $\{1, 2, 3\}$ 对应 $\{(1,2), (2,3), (3,4)\}$，构成一棵生成树。剩余边 $\{4, 5, 6\}$ 对应 $\{(1,4), (1,3), (2,4)\}$，也构成一棵生成树。