c++

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
const int N=1005;
int T,n,f[N][N],a[N][N],cnt;
vector<pair<int,int> >e;
pair<int,int> find(int a,int b){
	while (1){
		cout<<"? "<<a<<' '<<b<<endl;
		int res;cin>>res;
		if (res==a) break;
		b=res;
	}
	return {a,b};
}
void solve(){
	cin>>n;
	for (int i=n;i>1;i--){
		int x=1;
		while (1){
			if (x==i) break;
			pair<int,int>P=find(x,i);
			if (!f[P.fr][P.sc]){
				f[P.fr][P.sc]=1,f[P.sc][P.fr]=1;
				e.push_back({P.fr,P.sc}),cnt++;
			}
			if (cnt>=n-1) break;
			x=P.sc;
		}
		if (cnt>=n-1) break;
	}
	cout<<"! ";
	for (auto i:e) cout<<i.fr<<' '<<i.sc<<' ',f[i.fr][i.sc]=f[i.sc][i.fr]=0;cout<<endl;
	e.clear(),cnt=0;
}
signed main(){
	int t;cin>>t;
	while (t--) solve();
	return 0;
}

d:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define lowbit(i) (i&(-i))
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=6e5+5;
int T=read(),n,a[N],to[N],e[N],ne[N],ls[N],c[N],tip;
void add(int x,int k){
	for (int i=x;i<=n*2;i+=lowbit(i)) c[i]+=k;
}
int query(int x){
	int res=0;
	for (int i=x;i;i-=lowbit(i)) res+=c[i];
	return res;
}
signed main(){
	while (T--){
		n=read();tip=0;
		for (int i=1;i<=n;i++) a[i]=read(),to[a[i]]=-1;
		for (int i=1;i<=n*2;i++) ne[i]=-1,ls[i]=-1,e[i]=0,add(i,(i&1)?1:-1);int c=0;
		for (int i=1;i<=n;i++){
			if (to[a[i]]==-1){c++;
				ne[tip]=tip+1,e[++tip]=a[i],ls[tip]=tip-1;
				to[a[i]]=tip;
			}
			else if (query(to[a[i]])&1){
				if (ne[to[a[i]]]==-1) continue;
				if (e[to[a[i]]]<e[ne[to[a[i]]]]){
					e[to[a[i]]]=0,ne[ls[to[a[i]]]]=ne[to[a[i]]],ls[ne[to[a[i]]]]=ls[to[a[i]]];
					add(to[a[i]],1),add(2*n+1,-1);
					ne[tip]=tip+1,e[++tip]=a[i],ls[tip]=tip-1;
					to[a[i]]=tip;
				}
			}
			else{
				if (ne[to[a[i]]]==-1) continue;
				if (e[to[a[i]]]>e[ne[to[a[i]]]]){
					e[to[a[i]]]=0,ne[ls[to[a[i]]]]=ne[to[a[i]]],ls[ne[to[a[i]]]]=ls[to[a[i]]];
					add(to[a[i]],1),add(2*n+1,-1);
					ne[tip]=tip+1,e[++tip]=a[i],ls[tip]=tip-1;
					to[a[i]]=tip;
				}
			}
		}
		cout<<c<<'\n';
		for (int i=1;i<=2*n;i++){
			if (e[i]) cout<<e[i]<<' ';
		}cout<<'\n';
	}
	return 0;
}