Description

Bookworm is organizing his $n$ gold medals, and he finds that all the medals are magnetic. Formally, each medal belongs to a type of magnetic pole, and there are many types of poles. If two adjacent medals have the same pole, they repel each other; otherwise, they attract each other.

Bookworm does not know the pole of each medal. He can only find out whether two medals have the same pole or different poles by bringing them close. In other words, you may perform at most $Q$ interactions. In each interaction, you ask the judge two numbers $x,y$, and the judge returns whether the $x$-th medal and the $y$-th medal repel or attract. The medals are numbered from $0$ to $n-1$.

Bookworm wants to arrange his medals into a permutation such that every pair of adjacent medals attracts each other. Please help him output any valid permutation, or report that there is no solution.

Interaction Format

This problem contains multiple test cases. The first line of input contains an integer $T$, representing the number of test cases.

For each test case, the first line contains two integers $n,Q$, representing the number of medals and the upper limit of interactions.

If you need to make a query to the judge, output one line with two integers $x,y$ separated by spaces and flush the buffer. How to flush the buffer is described in the hint below. Then, read an integer $ret$ from standard input. If $ret=1$, the $x$-th medal and the $y$-th medal attract; if $ret=0$, they repel.

If you have determined that there is no solution, output a line with a single integer $-1$ and flush the buffer. Then this test case ends, and you should proceed to the next test case.

If you have determined that a solution exists, first output a line with a single integer $n$, then output any valid permutation of the medals on the next line, and flush the buffer. Then this test case ends, and you should proceed to the next test case.

After processing all $T$ test cases, you should terminate the program immediately. Extra output may cause RE.

Input Format

See "Interaction Format".

Output Format

See "Interaction Format".

2
3 100

1

1

1


2 100

0

0 1

0 2

1 2

3
0 1 2

0 1

-1

Hint

Explanation of Sample 1

There are two test cases in the sample. In the first test case, there are three medals. After three interactions, it is known that their poles are all different, so any permutation is correct.

In the second test case, the two medals have the same pole, so there is no solution.

Constraints

This problem uses bundled tests. The constraints are shown in the table below:

For all test cases, $2\le n\le5\times10^4$, $1\le T\le 5\times 10^4$, $\sum Q\le 10^5$.

Notes

You may use the following statements to flush the buffer:

• For C/C++：fflush(stdout);
• For C++：std::cout << std::flush;
• For Java：System.out.flush();
• For Python：stdout.flush();
• For Pascal：flush(output);
• For other languages, please refer to the corresponding language documentation.
• In particular, for C++, using std::endl instead of '\n' when printing a newline can also flush the buffer automatically.

Translated by ChatGPT 5