P7045 "MCOI-03" Gold Medal

**This is an interactive problem.** Bookworm has many gold medals.

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.

See "Interaction Format".

See "Interaction Format".

### 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: | Test Point ID | $Q=$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\frac{n(n-1)}{2}$ | $n\ge 4$ | $10$ | | $2$ | $2n-2$ | Each pole type has at most $2$ medals | $20$ | | $3$ | $2n-2$ | The number of pole types is at most $3$ | $20$ | | $4$ | $3n$ | None | $20$ | | $5$ | $2n-2$ | None | $30$ | 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