题目描述

$\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$ 条边也应构成一棵生成树。

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

提示

对于第一组样例，边 $\{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)\}$，也构成一棵生成树。