Telephone Network

A telephone company wants to build a new telephone network in a city. Every person in the city should be able to call every other person. Building a direct connection between every pair of persons is impossible, so the company uses a network made of several layers.

The network switch in layer $j$ is written $S(j)$. A switch $S(0)$ consists of one input, one output and a cable that connects the input to the output. A switch $S(j)$ with $j > 0$ consists of $2^j$ inputs, $2^j$ outputs and two switches $S(j-1)$. Input $i$ of $S(j)$ ($0 \le i < 2^j$) is connected by a cable to input $i \bmod 2^{j-1}$ of each of the two switches $S(j-1)$. Output $i$ of $S(j)$ is connected the same way to output $i \bmod 2^{j-1}$ of each of the two switches $S(j-1)$.

Consider a network whose outermost layer is a single switch $S(n)$. From any input and any output of $S(n)$ there is exactly one path to each of the $S(0)$ switches, so any input of $S(n)$ can be connected to any of its outputs, and naming the $S(0)$ switch that carries the connection fixes the whole path.

The $S(0)$ switches inside $S(n)$ are numbered $0$ to $2^n - 1$. Switch number $i$ is defined as follows. Write $i$ in binary as $b_{n-1}b_{n-2}\dots b_0$. These bits describe a path from an input of $S(n)$ down to switch number $i$: for each $j$, $b_j = 0$ means the path leaves $S(j+1)$ into the first of the two switches $S(j)$ it consists of, and $b_j = 1$ means it leaves into the second one. The path ends at the same $S(0)$ switch no matter which input of $S(n)$ it starts from, and that switch is the one numbered $i$.

Several connections are sometimes needed at the same time. To avoid interference, every input and every output of every switch $S(j)$ ($0 \le j \le n$) may be used by at most one connection. Given a set of connection requests, route every request so that no two connection paths share an input or an output of any switch.

The first line contains a positive integer, the number of test cases, at most $100$. Each test case follows in this form.

• One line with two integers $n$ ($1 \le n \le 16$) and $m$ ($1 \le m \le 2^n$): the layer of the outermost switch and the number of connection requests.
• $m$ lines, the $i$-th with two integers $a_i$ and $b_i$ ($0 \le a_i, b_i < 2^n$), a request to connect input $a_i$ of $S(n)$ to output $b_i$. The values $a_i$ are pairwise distinct, and the values $b_i$ are pairwise distinct as well.

For each test case, print one line with $m$ integers $s_1, \dots, s_m$, where $s_i$ is the number of the $S(0)$ switch that carries the connection from input $a_i$ to output $b_i$. The $m$ connection paths must be pairwise disjoint, and at least one such routing always exists.

Several routings are usually valid, so print the canonical one. It is defined layer by layer, from the outermost layer inward. In layer $j$ every request enters one of the two switches $S(j-1)$ that the switch $S(j)$ holding it consists of. Write the choices of that layer as the bit string $c_1c_2\dots c_m$, where $c_i$ is $0$ for the first of the two switches and $1$ for the second, so $c_i$ is bit $j-1$ of $s_i$. Start from all valid routings and keep the ones whose bit string for layer $n$ is smallest in lexicographic order. Among those keep the ones whose bit string for layer $n-1$ is smallest, and continue down to layer $1$. Exactly one routing survives.

The number of an $S(0)$ switch spells out its path. For $n = 3$, switch number $5$ has bits $b_2b_1b_0 = 101$, so the path takes the second $S(2)$ inside $S(3)$, then the first $S(1)$ inside that $S(2)$, then the second $S(0)$ inside that $S(1)$.