「MCOI-03」金牌

**这是一道交互题**。 书虫有很多块金牌！

书虫正在整理他的 $n$ 块金牌，他发现所有金牌都是有磁性的！形式地说，每块金牌属于一种磁极，**磁极有很多种**。两块相邻的金牌磁极相同则相互排斥，不同则相互吸引。 书虫不知道每块金牌的磁极，他只能通过把两块金牌靠近的方式得知它们是相同磁极还是不同磁极。换句话说，你可以进行不超过 $Q$ 次交互，每次向交互库询问两个数 $x,y$，交互库会返回第 $x$ 块金牌和第 $y$ 块金牌是排斥还是吸引。金牌从 $0$ 到 $n-1$ 编号。 书虫希望把他的金牌排成一个排列，满足任意两块相邻的金牌都相吸引，请你帮他排出 **任意一个** 合法的排列，或者告诉他无解。 ### 交互格式 **本题包含多组数据**。输入的第一行包含一个整数 $T$, 代表数据组数。 对于每一组数据，第一行读入两个整数 $n,Q$，代表金牌的数量和交互次数上限。 如果你需要向交互库发起询问，请向标准输出中输出一行以空格隔开的两个整数 $x,y$ 并 **清空缓冲区**。关于如何清空缓冲区，在下面的提示中有说明。接下来，从标准输入中读入一个整数 $ret$。如果 $ret=1$ 表示第 $x$ 块金牌和第 $y$ 块金牌吸引，如果 $ret=0$ 表示它们排斥。 如果你已经确定无解，请输出一行一个整数 $-1$ 并 **清空缓冲区**。然后本组数据结束，你应该接下来处理下一组数据。 如果你已经确定有解，请先输出一行一个整数 $n$，接下来一行输出 **任意一组** 合法的金牌排列，并 **清空缓冲区**。然后本组数据结束，你应该接下来处理下一组数据。 $T$ 组数据处理完之后你应该立即结束程序，多余的输出可能导致 RE。

见「交互格式」。

见「交互格式」。

2
3 100

1

1

1


2 100

0

0 1

0 2

1 2

3
0 1 2

0 1

-1

### 样例 1 解释 样例中有两组数据。对于第一组数据，共有三块金牌，通过三次交互得知，它们的磁极都互不相同，那么任意一种排列都是正确的。 对于第二组数据，两块金牌的磁极相同，所以无解。 ### 数据规模与约定 **本题使用捆绑测试**，数据范围如下表： | 测试点编号 | $Q=$ | 特殊性质 | 得分 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\frac{n(n-1)}{2}$ | $n\ge 4$ | $10$ | | $2$ | $2n-2$ | 一种磁极最多只有 $2$ 块金牌 | $20$ | | $3$ | $2n-2$ | 磁极的种类不超过 $3$ 种 | $20$ | | $4$ | $3n$ | 无 | $20$ | | $5$ | $2n-2$ | 无 | $30$ | 对于全部数据，$2\le n\le5\times10^4$，$1\le T\le 5\times 10^4$，$\sum Q\le 10^5$。 ### 提示 你可以使用如下语句来清空缓冲区： - 对于 C/C++：```fflush(stdout);``` - 对于 C++：```std::cout << std::flush;``` - 对于 Java：```System.out.flush();``` - 对于 Python：```stdout.flush();``` - 对于 Pascal：```flush(output);``` - 对于其他语言，请自行查阅对应语言的帮助文档。 - 特别的，对于 C++ 语言，在输出换行时使用 ```std::endl ``` 而不是 ```'\n'```，也可以自动刷新缓冲区。