#413 Tangled Wires

Statement

Statement language

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 must connect slots and , and wire must connect slots and . Unplug the endpoints in slots and and plug each endpoint into the other slot. After the operation, wire connects slots and , and wire connects slots and .

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.

Input

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

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

Output

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

Constraints

$1 \leq T \leq 200\,000$ .
$1 \leq N \leq 200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	12	The sum of $N$ over all test cases does not exceed $20$ .
2	31	The sum of $N$ over all test cases does not exceed $2\,000$ .
3	57	No additional constraints.

Samples

Input

Output

1 1 2 2
1 2 2 3 3 1

In the first test case, one operation on the two wires produces the sequence $[1,1,2,2]$ .

In the second test case, one operation on wires $2$ and $3$ produces the printed sequence.