Telephone Network#2457

Telephone Network

1 second

64 megabytes

Very hard

A telephone company wants to build a new telephone network in a city. The company aims for every person in the city to be able to call any other person. Of course, direct connections between every pair of people are not possible. Instead, the company uses a network made up of several layers.

We denote a network switch in layer $j$ by $S (j)$ . A switch $S (0)$ consists of one input, one output, and a cable connecting the input to the output. A switch $S (j)$ with $j > 0$ j > 0 consists of $2^{j}$ 2^j inputs, $2^{j}$ 2^j outputs, and two switches $S (j - 1)$ S(j-1). Input $i$ of $S (j)$ ( $0 \leq i < 2^{j}$ 0 \leq i < 2^j) is connected via a cable to the inputs $i mod 2^{j - 1}$ i \bmod 2^{j-1} of each of the two switches $S (j - 1)$ S(j-1). Similarly, output $i$ of $S (j)$ is connected to the outputs $i mod 2^{j - 1}$ i \bmod 2^{j-1} of each of the two switches $S (j - 1)$ S(j-1).

The connections between a switch $S (j)$ and the two switches $S (j - 1)$ S(j-1) it consists of.

We are considering a network with one switch $S (n)$ in the outermost layer. It can be shown that any input and output of switch $S (n)$ has a unique connection path to any of the $S (0)$ switches. Therefore, any input of $S (n)$ can be connected to any output, and the connection path is uniquely determined by specifying through which switch $S (0)$ the connection is established.

We number the switches $S (0)$ belonging to $S (n)$ from $0$ to $2^{n} - 1$ 2^{n}-1. The $i$ -th switch $S (0)$ is defined as follows. Write the number $i$ in binary as $b_{n - 1} b_{n - 2} \dots b_{0}$ b_{n-1}b_{n-2}\ldots b_0. This defines a path from an input of $S (n)$ to the $i$ -th switch $S (0)$ using the following procedure: for each $j$ , $b_{j} = 0$ b_j = 0 means the path continues at the first $S (j)$ switch to which it is directly connected, and $b_{j} = 1$ b_j = 1 means it continues at the second $S (j)$ switch. Note that regardless of which input of $S (n)$ is chosen, this path arrives at the same $S (0)$ switch, which is assigned the number $i$ . See the figure below the sample data for more details on how the numbering works.

Sometimes multiple connections are needed at the same time. To avoid interference, each input and output of all switches $S (j)$ ( $0 \leq j \leq n$ 0 \leq j \leq n) can be used by at most one connection. Given a set of connection requests, can you find connection paths for each request such that the paths are disjoint?

Input

The first line contains a positive integer $t$ ( $1 \leq t \leq 100$ 1 \leq t \leq 100): the number of test cases. After that, for each test case:

One line with two integers $n$ ( $1 \leq n \leq 16$ 1 \leq n \leq 16) and $m$ ( $1 \leq m \leq 2^{n}$ 1 \leq m \leq 2^n): the layer of the outermost switch and the number of connection requests.
$m$ lines, each containing two integers $a_{i}$ a_i and $b_{i}$ b_i ( $0 \leq a_{i}, b_{i} < 2^{n}$ 0 \leq a_i, b_i < 2^n). Each such line represents a connection request from input $a_{i}$ a_i of $S (n)$ to output $b_{i}$ b_i of $S (n)$ . The integers $a_{i}$ a_i are all distinct, and the integers $b_{i}$ b_i are also all distinct.

Output

For each test case:

One line with $m$ integers $s_{1}, \dots, s_{m}$ s_1, \ldots, s_m, where $s_{i}$ s_i is the number of the $S (0)$ switch through which the connection from input $a_{i}$ a_i to output $b_{i}$ b_i is established.

The connection paths must be disjoint. You may print any valid solution, and you may assume that there is at least one valid solution.

Hint

A possible connection scheme for the second sample case, with used cables shown in bold.

Note: Special judge problem; you may get Wrong Answer if your output is in the wrong format.

Examples

Example 1