#include"explore.h"
#include<bits/stdc++.h>
#define Ma 10000000
#define N 200000
using namespace std;
int n,m,B,fl[N+1],logn[N+1],pa[N+1],a[N+1],b[N+1],pb,gfl[N+1],cd[N+1],tfl[N+1],ft[N+1];
int t[N+1],pt,inq[N+1],afl[N+1],tg[N+1];
int q0[N+1],p0;
int ma[2][N+1],gg;
int ha[Ma][2];
set<pair<int,int> > se;
unordered_set<long long>nse;
queue<int>qu;
vector<int>ve[N+1];
int rd(){return rand();}
//int rd(){return rand()*32768+rand();}
long long hsh(int x,int y){if(x>y)swap(x,y);return x*1000000ll+y;}
void cal0(){
	for(int i=1;i<n;i++){
		modify(i-1),fl[i]^=1;
		for(int j=i+1;j<=n;j++){
			if(query(j-1)!=fl[j])fl[j]^=1,report(i-1,j-1);
		}
	}
}
void cal1(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	for(int i=0;i<=logn[n];i++){
		for(int j=0;j<n;j++)if(j&(1<<i))modify(j),fl[j]^=1;
		for(int j=0;j<n;j++)if(query(j)!=fl[j])fl[j]^=1,pa[j]|=(1<<i);
	}
	for(int i=0;i<n;i++)if(i<pa[i])report(i,pa[i]);
}
void cal2(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	for(int i=0;i<=logn[n];i++){
		for(int j=0;j<n;j++){
			if(j&&query(j)!=fl[j])fl[j]^=1,pa[j]|=(1<<i);
			if(j&(1<<i))modify(j),fl[j]^=1;
		}
		for(int j=0;j<n;j++)if(j&(1<<i))modify(j);
		memset(fl,0,sizeof(fl));
	}
	for(int j=1;j<n;j++)report(j,pa[j]);
}
bool fnd(int x,int y){
	return ma[0][x]==y||ma[1][x]==y||ma[0][y]==x||ma[1][y]==x;
}
void gad(int x,int y){
	se.insert(make_pair(x,y));
	se.insert(make_pair(y,x));
}
bool gnd(int x,int y){
	return (se.find(make_pair(x,y))!=se.end());
}
void nad(int x,int y){
	if(ma[0][x]!=-1)ma[1][x]=y;
	else ma[0][x]=y;
	if(ma[0][y]!=-1)ma[1][y]=x;
	else ma[0][y]=x;
}
bool Qu(int x){
	gg++;
	return query(x);
}
void cal3(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	for(int i=0;i<=logn[n];i++){
		for(int j=0;j<n;j++)if(j&(1<<i))modify(j),fl[j]^=1;
		for(int j=0;j<n;j++)if(query(j)!=fl[j])fl[j]^=1,pa[j]|=(1<<i);
	}
	for(int j=0;j<n;j++){
		modify(j),fl[j]^=1;
		if(pa[j]<n&&query(pa[j])!=fl[pa[j]]){
//			fl[pa[j]]^=1;
			if(se.find(make_pair(pa[j],j))==se.end()&&se.find(make_pair(j,pa[j]))==se.end())report(j,pa[j]),se.insert(make_pair(j,pa[j]));
			if(check(j))qu.push(pa[j]),inq[j]=1,pa[pa[j]]^=j;
		}
		modify(j),fl[j]^=1;
	}
	int lan=n;
	while(!qu.empty()){
		int nt=qu.front();
//		if(nt==59880){
//			cout<<"aa\n";
//		}
		qu.pop(),lan--;
		if(inq[nt])continue;
		if(inq[nt]!=1){
			modify(nt),fl[nt]^=1;
			if(pa[nt]<n&&query(pa[nt])!=fl[pa[nt]]){
				if(se.find(make_pair(pa[nt],nt))==se.end()&&se.find(make_pair(nt,pa[nt]))==se.end())report(nt,pa[nt]),se.insert(make_pair(nt,pa[nt]));
				if(check(nt)){
					pa[pa[nt]]^=nt;
					qu.push(pa[nt]);
					inq[nt]=1;
				}
				
			}
			modify(nt),fl[nt]^=1;
		}
		
		
	}
}
void calc(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	B=max(1,n/100);
	int tn=n,ncol=1;
	while(tn){
//		if(tn==32768){
//			cout<<"aa";
//		}
//		cout<<tn<<endl;
		if(tn>=100000)B=max(1,tn/10);
//		if(tn>=100000)B=max(1,(int)(sqrt(tn)*log(tn)*log(log(tn))));
		else B=max(1,(int)(sqrt(tn)*log(tn)));
		if(n%10==4)B=max(1,(int)(sqrt(n)));
		B=min(B,tn);
		pt=0;ncol++;
		for(int i=0;i<n;i++)if(!afl[i])t[++pt]=i;
		for(int i=2;i<=pt;i++)swap(t[i],t[rd()%i+1]);
		for(int i=1;i<=B;i++)ft[t[i]]=i,modify(t[i]),fl[t[i]]^=1,tfl[t[i]]=ncol;
		p0=0;
		for(int i=0;i<n;i++){
			if(afl[i])continue;
			tg[i]=0;int lg=0;
			for(int j=0;j<ve[i].size();j++){
				if(tfl[ve[i][j]]==ncol)tg[i]^=1,lg^=(ft[ve[i][j]]-1);
			}
			if((query(i)!=fl[i])^tg[i]){
				fl[i]^=1,q0[++p0]=i,pa[p0]=lg;
			}
		}
//		cout<<tn<<" "<<p0<<" "<<B<<endl;
//		for(int i=1;i<=p0;i++)pa[i]=0;
		for(int i=0;i<=logn[B];i++){
			for(int j=1;j<=B;j++)if((j-1)&(1<<i))modify(t[j]),fl[t[j]]^=1;
			for(int j=1;j<=p0;j++)if(query(q0[j])!=fl[q0[j]])fl[q0[j]]^=1,pa[j]^=(1<<i);
		}
		for(int i=1;i<=B;i++)if(query(t[i])!=fl[t[i]])fl[t[i]]^=1;
		for(int i=1;i<=p0;i++){
//			if(q0[i]==9456&&tn==72645){
//				cout<<"aa\n";
//			}
			if(pa[i]>=B)continue;
			modify(q0[i]),fl[q0[i]]^=1;
			int nt=t[pa[i]+1];
			if(tfl[nt]){
				long long nh=hsh(q0[i],nt);
				if((nse.find(nh)==nse.end())&&query(nt)!=fl[nt]){
					report(q0[i],nt);
					ve[q0[i]].push_back(nt),ve[nt].push_back(q0[i]);
					nse.insert(nh);
				}
			}
			modify(q0[i]),fl[q0[i]]^=1;
		}
		for(int i=1;i<=B;i++){
			if(check(t[i]))afl[t[i]]=1,tn--;
		}
		for(int i=1;i<=p0;i++){
			if(tfl[q0[i]]!=ncol&&check(q0[i]))afl[q0[i]]=1,tn--;
		}
//		for(int i=1;i<=n;i++)if(query(i)!=fl[i])fl[i]^=1;
	}
}
void explore(int NN,int M){
	srand(7);
	n=NN,m=M;
//	calc();return;
	if(n<=500)cal0();
	else if(n%10==8)cal1();
	else if(n%10==7)cal2();
	else if(n%10>=5)cal3();
	else calc();
	return;
}
/*
100 100 100
8 7
0 6
6 4
4 5
5 3
3 7
7 2
2 1

100 100 100
7 9
0 6
0 4
0 3
6 1
4 3
3 1
4 2
2 5
5 1
*/