Problem Description

$\mathit{tarjen}$ is playing a game of merging two trees into one graph. He took two trees with $n$ vertices each and merged them into an undirected unweighted graph $G = (V, E)$ with $n$ vertices and $m = 2n - 2$ edges. However, he found that he cannot restore this graph back into two trees. Please help him.

Formally, you need to partition all edges into two sets $T$ and $E \setminus T$, such that both $T$ and $E \setminus T$ form a spanning tree of $G$.

You may output any valid solution. It is guaranteed that a valid solution always exists.

Note: The graph may contain multiple edges, but it is guaranteed to have no self-loops.

Input Format

The first line contains an integer $T$ ($1 \le T \le 5000$), the number of test cases. Then follow $T$ test cases, each described as follows.

• The first line contains an integer $n$ ($2 \le n \le 5000$), the number of vertices.
• The next $2n - 2$ lines each contain two integers $u, v$ ($1 \le u, v \le n$, $u \ne v$), describing an edge. Edges are numbered from $1$ to $2n - 2$ in the input order.

It is guaranteed that $\sum n$ does not exceed $10000$.

Output Format

For each test case, output $n - 1$ integers (in increasing order), indicating the edge indices included in the first spanning tree. The remaining $n - 1$ edges should also form a spanning tree.

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

Hint

For the first sample, edges $\{1, 2\}$ correspond to $\{(1,2), (2,3)\}$ and form a spanning tree. The remaining edges $\{3, 4\}$ correspond to $\{(1,3), (1,2)\}$ and also form a spanning tree.

For the second sample, edges $\{1, 2, 3\}$ correspond to $\{(1,2), (2,3), (3,4)\}$ and form a spanning tree. The remaining edges $\{4, 5, 6\}$ correspond to $\{(1,4), (1,3), (2,4)\}$ and also form a spanning tree.

Translated by ChatGPT 5