#include<bits/stdc++.h>
#include "wheretoreach.h"
using namespace std;
int al,ed;
int tims;
vector<int> vec;
vector<int> tv,ct;
int rk[100005];
int vis[100005];
int tadd(int u){
	vis[rk[u]]=1;
	return add(rk[u]);
}
int tremove(int u){
	if(!vis[rk[u]]) return 0;
	vis[rk[u]]=0;
	return remove(rk[u]);
}
void treport(int u,int v){
	tims++;
	report(rk[u],rk[v]);
}
void bs(int l,int r,vector<int> nt){
	if(!nt.size()) return;
	if(tims==al-1) return;
	// printf("lr %d %d\nnt:",l,r);
	// for(int i=0;i<nt.size();i++) printf("%d ",nt[i]);puts("");
	if(l==r){
		for(int i=0;i<nt.size();i++){
			// printf("REPORTER %d %d\n",nt[i],tv[l]);
			treport(nt[i],tv[l]);
		}
		return;
	}
	vector<int> lt,rt;
	int mid=(l+r)>>1;
	if(l!=0||r!=ed)
	for(int i=l;i<=mid;i++) tadd(tv[i]);
	for(int i=0;i<nt.size();i++){
		int p=tadd(nt[i]);
		if(p>1) lt.push_back(nt[i]);
		else rt.push_back(nt[i]);
		tremove(nt[i]);
	}
	for(int i=l;i<=mid;i++) tremove(tv[i]);
	bs(l,mid,lt);
	if(tims==al-1) return;
	if(lt.size()){
		for(int i=mid+1;i<=r;i++) tadd(tv[i]);
		for(int i=0;i<lt.size();i++){
			int p=tadd(lt[i]);
			if(p>1) rt.push_back(lt[i]);
			tremove(lt[i]);
		}
		for(int i=mid+1;i<=r;i++) tremove(tv[i]);
	}
	bs(mid+1,r,rt);
}
void mian(){
	tv.clear();ct.clear();
	for(int i=1;i<=al;i++) vis[i]=0;
	for(int i=0;i<vec.size();i++){
		int p=tadd(vec[i]);
		if(p>1) ct.push_back(vec[i]),tremove(vec[i]);
		else tv.push_back(vec[i]);
	}
	// for(int i=0;i<tv.size();i++) printf("%d ",tv[i]);puts("");
	if(!ct.size()) return vec.clear();
	int mid=(0+tv.size())>>1;
	ed=tv.size()-1;
	for(int i=mid+1;i<tv.size();i++) tremove(tv[i]);
	bs(0,tv.size()-1,ct);
	vec=ct;
	if(tims==al-1) vec.clear();
}
void solve(int n){
	al=n;
	for(int i=1;i<=n;i++) rk[i]=i,vec.push_back(i);
	mt19937 lrher(time(0));
	shuffle(rk+1,rk+1+n,lrher);
	while(vec.size()) mian();
}