꼬인 전선

$2N$개의 칸이 왼쪽부터 $1,2,\cdots,2N$의 번호를 가진다. 각 칸에는 정확히 하나의 전선 끝이 꽂혀 있다. 전선은 $1,2,\cdots,N$의 번호를 가지며, $i$번 전선의 두 끝은 처음에 $a_i$번 칸과 $b_i$번 칸에 꽂혀 있다.

다다스는 다음과 같은 전선 풀기 연산을 원하는 만큼 수행할 수 있다.

서로 다른 두 전선 $x,y$와 네 칸 $p_1<p_2<p_3<p_4$를 고른다. 연산 직전에 $x$번 전선이 $p_1$번 칸과 $p_3$번 칸을 연결하고, $y$번 전선이 $p_2$번 칸과 $p_4$번 칸을 연결해야 한다. $p_2$번 칸과 $p_3$번 칸에 꽂힌 전선 끝을 뽑아 서로의 칸에 다시 꽂는다. 연산 후에는 $x$번 전선이 $p_1$번 칸과 $p_2$번 칸을 연결하고, $y$번 전선이 $p_3$번 칸과 $p_4$번 칸을 연결한다.

현재 배치를 나타내는 길이 $2N$의 수열 $C$를 다음과 같이 정의한다. $p$번 칸에 $i$번 전선의 끝이 꽂혀 있다면 $C_p=i$이다.

전선 풀기 연산을 $0$번 이상 수행하여 만들 수 있는 수열 $C$ 중 사전 순으로 가장 작은 것을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 한 줄에 사전 순으로 가장 작은 수열 $C_1,C_2,\cdots,C_{2N}$을 공백으로 구분하여 출력한다.

• $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$).
• $a_1,b_1,a_2,b_2,\cdots,a_N,b_N$은 모두 서로 다르다.
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.