꼬인 전선

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

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

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

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

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

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

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

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

• $1 \leq T \leq 200\,000$.
• $1 \leq N \leq 200\,000$.
• $1\le {}_{}$ ().