P16921 [JLCPC 2026] Split Tree.

$\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.

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$.

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.

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