tarjen 正在玩一个将两棵树合并为一个图的游戏。

他将两棵拥有 $n$ 个顶点的树合并为一个拥有 $n$ 个顶点和 $m = 2n - 2$ 条边的无向无权图 $G = (V, E)$。

但现在他无法将这个图重新分解回两棵树——请帮帮他！

正式地，将所有边划分为两个集合 $T$ 和 $E \setminus T$，使得 $T$ 和 $E \setminus T$ 均构成 $G$ 的生成树。

你可以输出任意一种合法的划分方案。保证存在至少一种合法的划分方案。

图中可能包含重边，但不包含自环。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 5000$) — 测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$ ($2 \le n \le 5000$) — 顶点的数量。

接下来的 $2n - 2$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \ne v$)，描述一条边。边按输入顺序从 $1$ 到 $2n - 2$ 进行编号。

所有测试用例中 $n$ 的总和不超过 $10000$。

输出格式

对于每个测试用例，按升序输出 $n - 1$ 个整数，表示第一棵生成树中包含的边编号。剩下的 $n - 1$ 条边也必须构成一棵生成树。

样例

输入格式 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

说明

第一个测试用例：边 $\{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)\}$，也构成一棵生成树。