전화망

어느 전화 회사가 도시에 새 전화망을 놓으려고 한다. 도시의 모든 사람이 서로 통화할 수 있게 하는 것이 목표다. 모든 사람 쌍을 직접 잇는 것은 불가능하므로, 회사는 여러 층으로 이루어진 망을 쓴다.

$j$층의 교환기를 $S(j)$라고 쓴다. $S(0)$은 입력 하나, 출력 하나, 그리고 그 입력과 출력을 잇는 케이블 하나로 이루어진다. $j > 0$인 $S(j)$는 입력 $2^j$개, 출력 $2^j$개, 그리고 $S(j-1)$ 두 개로 이루어진다. $S(j)$의 입력 $i$($0 \le i < 2^j$)는 두 $S(j-1)$ 각각의 입력 $i \bmod 2^{j-1}$과 케이블로 이어져 있다. 출력도 마찬가지여서, $S(j)$의 출력 $i$는 두 $S(j-1)$ 각각의 출력 $i \bmod 2^{j-1}$과 이어져 있다.

가장 바깥 층이 $S(n)$ 하나인 망을 생각하자. $S(n)$의 어떤 입력에서도, 어떤 출력에서도 각 $S(0)$까지 가는 경로는 하나뿐이다. 그래서 $S(n)$의 입력은 어느 출력과도 연결할 수 있고, 연결이 어느 $S(0)$을 지나는지만 정하면 경로 전체가 하나로 정해진다.

$S(n)$ 안의 $S(0)$에는 $0$부터 $2^n - 1$까지 번호를 붙인다. 번호가 $i$인 $S(0)$은 다음과 같이 정한다. $i$를 이진법으로 $b_{n-1}b_{n-2}\dots b_0$이라고 쓰자. 이 비트열은 $S(n)$의 입력에서 번호가 $i$인 $S(0)$까지 내려가는 경로를 나타낸다. 각 $j$에 대해 $b_j = 0$이면 경로는 $S(j+1)$을 이루는 두 $S(j)$ 중 첫 번째로 내려가고, $b_j = 1$이면 두 번째로 내려간다. $S(n)$의 어느 입력에서 시작하든 이 경로는 같은 $S(0)$에 도착하며, 그 $S(0)$의 번호가 $i$다.

여러 연결이 동시에 필요할 때가 있다. 간섭을 막기 위해 모든 $S(j)$($0 \le j \le n$)의 입력과 출력은 각각 많아야 한 연결만 쓸 수 있다. 연결 요청이 주어질 때, 어떤 두 경로도 같은 교환기의 입력이나 출력을 함께 쓰지 않도록 모든 요청의 경로를 정하라.

첫 줄에 테스트 케이스의 수를 나타내는 양의 정수가 주어진다. 이 값은 $100$ 이하다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

• 한 줄에 두 정수 $n$($1 \le n \le 16$)과 $m$($1 \le m \le 2^n$). $n$은 가장 바깥 교환기의 층이고, $m$은 연결 요청의 수다.
• 다음 $m$개 줄 중 $i$번째 줄에 두 정수 $a_i$와 $b_i$($0 \le a_i, b_i < 2^n$). $S(n)$의 입력 $a_i$를 출력 $b_i$에 연결하라는 요청이다. $a_i$는 서로 다르고, $b_i$도 서로 다르다.

각 테스트 케이스마다 한 줄에 정수 $m$개 $s_1, \dots, s_m$을 출력한다. $s_i$는 입력 $a_i$와 출력 $b_i$를 잇는 연결이 지나가는 $S(0)$의 번호다. $m$개의 경로는 서로 겹치지 않아야 하고, 그런 배정은 항상 하나 이상 존재한다.

유효한 배정은 보통 여러 개이므로, 다음과 같이 정한 표준 배정을 출력한다. 바깥 층부터 안쪽으로 한 층씩 정한다. 층 $j$에서 각 요청은 자신을 담고 있는 $S(j)$를 이루는 두 $S(j-1)$ 중 하나로 들어간다. 그 층의 선택을 비트열 $c_1c_2\dots c_m$으로 적는데, 첫 번째 $S(j-1)$로 들어가면 $c_i = 0$, 두 번째로 들어가면 $c_i = 1$이다. 즉 $c_i$는 $s_i$의 $j-1$번 비트다. 유효한 배정 전체에서 시작해, 층 $n$의 비트열이 사전순으로 가장 작은 배정만 남긴다. 그중에서 층 $n-1$의 비트열이 사전순으로 가장 작은 것만 남기고, 같은 방법을 층 $1$까지 이어간다. 마지막에는 배정이 정확히 하나 남는다.

$S(0)$의 번호는 그 자체가 경로를 알려준다. $n = 3$이고 번호가 $5$인 $S(0)$이라면 비트가 $b_2b_1b_0 = 101$이므로, 경로는 $S(3)$ 안의 두 번째 $S(2)$로, 그 $S(2)$ 안의 첫 번째 $S(1)$로, 그 $S(1)$ 안의 두 번째 $S(0)$으로 내려간다.