$$$tarjen$$$ is playing a game of combining two trees into one graph.
He took two trees on $$$n$$$ vertices and combined them into an undirected unweighted graph $$$G = (V, E)$$$ with $$$n$$$ vertices and $$$m = 2n - 2$$$ edges.
But now he cannot decompose the graph back into two trees — please help him!
Formally, partition all edges into exactly two sets $$$T$$$ and $$$E \setminus T$$$ such that both $$$T$$$ and $$$E \setminus T$$$ form spanning trees of $$$G$$$.
You may output any valid partition. It is guaranteed that a valid partition exists.
The graph may contain parallel edges but no self-loops.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.
For each test case:
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 input order.
The sum of $$$n$$$ over all test cases does not exceed $$$10000$$$.
For each test case, output $$$n - 1$$$ integers in ascending order — the edge indices included in the first spanning tree. The remaining $$$n - 1$$$ edges must also form a spanning tree.
231 22 31 31 241 22 33 41 41 32 4
1 2 1 2 3
First test case: edges $$$\{1, 2\}$$$ correspond to $$$\{(1,2), (2,3)\}$$$, forming a spanning tree. The remaining edges $$$\{3, 4\}$$$ correspond to $$$\{(1,3), (1,2)\}$$$, also forming a spanning tree.
Second test case: edges $$$\{1, 2, 3\}$$$ correspond to $$$\{(1,2), (2,3), (3,4)\}$$$, forming a spanning tree. The remaining edges $$$\{4, 5, 6\}$$$ correspond to $$$\{(1,4), (1,3), (2,4)\}$$$, also forming a spanning tree.
