题意简述
给你 \(n\) 个数，你不知道每个数的权值。
每次可以查询 \(x,y\) 表示查询 \(x,y\) 的权值是否相等，0 是 1 否。
你需要在 \(2n-2\) 次查询之内将这些数排成一个相邻两个数的权值不同的数列，并构造出来，或者报告无解。
分析
考虑在什么情况下会无解。
如果存在一种数使得等于该种数的数量超过了 \(\lceil\dfrac{n}{2}\rceil\)，容易发现你此时把剩下的数比这些数形成的空隙数量还要小，所以肯定无解，等价于 \(cnt-1>n-cnt\)。
这跟绝对众数的定义很相似啊！
使用摩尔投票法找到可能的绝对众数，询问次数 \(n-1\)。
然后把绝对众数依次和剩余的数查询一下，就能得出该绝对众数的出现次数了，然后就能判断有无解情况了。
那么如何构造合法答案呢？
第一轮做摩尔投票的时候，我们维护一个栈，表示暂时没法插入进去的下标的集合。初始把 \(1\) 压入栈内。显然，若栈非空，那么栈中的所有元素值相等，且当前数列的最后一个值就等于栈中的元素值（数列为空除外）。
现在要插进来一个元素，若该元素和栈中的元素不同，那么把栈顶弹出来，把当前下标和栈顶插到数列后面（两者插入顺序有先后关系）；若相同则直接压入栈内。
如果栈为空，那么与数列最后一个元素比较，执行上述流程。
算法结束后，栈中还会剩下零个或多个元素，且元素值等于候选众数。由于验证候选众数需要让该数和所有其他数都比较一遍，此时如果发现了数列中两个相邻的元素都不等于候选众数，那么把栈顶插入到这两个数之间并弹栈。注意你可以把元素插到最前或最后。
若栈中依然还有元素，那么无解；
证明：如果栈中的元素没有找到一个合适的位置插入，此时数列一定形如 12121，其中 1 为候选众数，2 为其他元素。容易发现此时已经达到了极限情况，且跟第一轮摩尔投票的决策无关。
否则一定有解，且当前解即为合法解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
using pii=pair<int,int>;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=5e4+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,Jiaohucishu;
inline int ask(int x,int y){
if(!x||!y||x==n+1||y==n+1)return 1;
cout<<x-1<<' '<<y-1<<endl;
return rd();//0 = 1 !=
}
int lft[maxn],rht[maxn];
void answer(){
cout<<n<<endl;
int r=rht[0],cnt=0;
while(r<=n)write(r-1,32),++cnt,r=rht[r];
assert(cnt==n);
cout<<endl;
}
vector<int>sta;
//将x插入到ed前面
inline void ins(int x,int ed=n+1){
rht[x]=ed,lft[x]=lft[ed];
lft[rht[x]]=x,rht[lft[x]]=x;
}
void init(){
sta.clear();
rht[0]=n+1,lft[n+1]=0;
rep(i,1,n)lft[i]=0,rht[i]=n+1;
}
inline void solve_the_problem(){
n=rd(),Jiaohucishu=rd();
init();
sta.emplace_back(1);
rep(i,2,n){
if(sta.empty()){
int x=lft[n+1];
int p=ask(x,i);
if(!p)sta.pb(i);
else ins(i);
continue;
}
int p=ask(sta.back(),i);
if(!p)sta.pb(i);
else{
ins(i);
ins(sta.back());
sta.pop_back();
}
}
int r=0,ok=1;
while(r<=n&&!sta.empty()){
int qr=rht[r];
int p=ask(qr,sta.back());
if(ok&&p)ins(sta.back(),qr),sta.pop_back();
r=qr,ok=p;
}
if(sta.empty())return answer();
cout<<-1<<endl;
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=rd();
while(_--)solve_the_problem();
}
/*
5
1 2 1 2 1
*/