#include<bits/stdc++.h>
#include "park.h"
using namespace std;
const int MAXN=1401;
int n;
struct Edge {
	int u,v;
	Edge(int _u=0,int _v=0): u(_u),v(_v) {}
};
inline int Query(int u,int v,vector <int> V) {
	static int buf[MAXN];
	fill(buf,buf+n,0);
	for(int i:V) buf[i]=1;
	buf[u]=buf[v]=1;
	return Ask(min(u,v),max(u,v),buf);
}
inline void ReportEdge(int u,int v) { Answer(min(u,v),max(u,v)); }
inline vector<Edge> Solve() {
	vector <int> V;
	vector <Edge> E;
	vector <int> inq(n,0);
	vector <vector<int>> adj(n);
	auto InsertNode=[&](int u) -> void {
		V.push_back(u),inq[u]=1;
	};
	auto LinkEdge=[&](int u,int v) -> void {
		assert(inq[u]&&inq[v]);
		adj[u].push_back(v);
		adj[v].push_back(u);
		E.push_back({u,v});
	};
	InsertNode(0);
	while((int)V.size()<n) {
		vector <int> outq,vis(n,0);
		for(int i=0;i<n;++i) if(!inq[i]) outq.push_back(i);
		int nw=outq.front();
		auto GetChain=[&](auto self,int l,int r) -> vector<int> {
			vector <int> bas=(l==0)?V:vector<int>{};
			if(Query(l,r,bas)) return {};
			int ul=0,ur=n-1;
			while(ul<ur) {
				int mid=(ul+ur)>>1;
				auto check=[&](int x) {
					vector <int> qry=bas;
					for(int i=0;i<=x;++i) qry.push_back(i);
					return Query(l,r,qry);
				};
				if(check(mid)) ur=mid;
				else ul=mid+1;
			}
			auto L=self(self,l,ur),R=self(self,ur,r);
			vector <int> ans;
			for(int i:L) ans.push_back(i);
			ans.push_back(ur);
			for(int i:R) ans.push_back(i);
			return ans;
		};
		vector <int> chain=GetChain(GetChain,0,nw),ans;
		chain.push_back(nw);
		auto FindNeighbors=[&](int u) -> void {
			auto MinLink=[&](auto self,vector <int> B) -> vector<int> {
				vector <int> vis(n,1),dfn;
				for(int i:B) vis[i]=0;
				int rt=B.front();
				auto dfs1=[&](auto self,int u) -> void {
					dfn.push_back(u),vis[u]=1;
					for(int v:adj[u]) if(!vis[v]) self(self,v);
				};
				dfs1(dfs1,rt);
				int l=0,r=dfn.size()-1;
				while(l<r) {
					int mid=(l+r)>>1;
					auto check=[&](int x) {
						vector <int> subt;
						for(int i=0;i<=x;++i) subt.push_back(dfn[i]);
						return Query(rt,u,subt);
					};
					if(check(mid)) r=mid;
					else l=mid+1;
				}
				vector <int> ans{dfn[r]};
				fill(vis.begin(),vis.end(),1);
				for(int i=0;i<(int)dfn.size();++i) if(i!=r) vis[dfn[i]]=0;
				for(int v:V) {
					if(vis[v]) continue;
					vector <int> ver;
					auto dfs2=[&](auto self,int u) -> void {
						ver.push_back(u),vis[u]=1;
						for(int v:adj[u]) if(!vis[v]) self(self,v);
					};
					dfs2(dfs2,v);
					if(Query(ver.front(),u,ver)) {
						vector <int> tmp=self(self,ver);
						for(int x:tmp) ans.push_back(x);
					}
				}
				return ans;
			};
			vector <int> Ne=MinLink(MinLink,V);
			InsertNode(u);
			for(int v:Ne) LinkEdge(u,v);
		};
		for(int i=0;i<(int)chain.size();++i) {
			int u=chain[i];
			FindNeighbors(u);
		}
	}
	return E;
}
void Detect(int T,int N) {
	n=N;
	vector <Edge> G=Solve();
	for(auto e:G) ReportEdge(e.u,e.v);
}