Tangled Wires

There are $2N$ slots numbered $1,2,\cdots,2N$ from left to right. Exactly one wire endpoint is plugged into each slot. The wires are numbered $1,2,\cdots,N$, and the two endpoints of wire $i$ are initially plugged into slots $a_i$ and $b_i$.

Dadas may perform the following untangling operation any number of times.

Choose two distinct wires $x,y$ and four slots $p_1<p_2<p_3<p_4$. Immediately before the operation, wire $x$ must connect slots $p_1$ and $p_3$, and wire $y$ must connect slots $p_2$ and $p_4$. Unplug the endpoints in slots $p_2$ and $p_3$ and plug each endpoint into the other slot. After the operation, wire $x$ connects slots $p_1$ and $p_2$, and wire $y$ connects slots $p_3$ and $p_4$.

Define a sequence $C$ of length $2N$ representing the current arrangement. If an endpoint of wire $i$ is plugged into slot $p$, then $C_p=i$.

Among all sequences $C$ obtainable after zero or more untangling operations, find the lexicographically smallest one.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_N\ b_N$

For each test case, print the lexicographically smallest sequence $C_1,C_2,\cdots,C_{2N}$ on one line, separated by spaces.

• $1 \leq T \leq 200\,000$.
• $1 \leq N \leq 200\,000$.
• $1 \leq a_i < b_i \leq 2N$ ($1 \leq i \leq N$).
• The values $a_1,b_1,a_2,b_2,\cdots,a_N,b_N$ are pairwise distinct.
• The sum of $N$ over all test cases does not exceed $200\,000$.