#include<bits/stdc++.h>
#include "wheretoreach.h"
using namespace std;
#define vec vector
#define pb push_back
#define eb emplace_back
#define siz(vec) ((int)(vec).size())
#define all(vec) (vec).begin(),(vec).end()
template<class T>
void operator +=(vec<T> &a,T b){a.push_back(b);}
template<class T>
void operator --(vec<T> &a){a.pop_back();}
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair
#define exc(exp) if(exp)continue;
#define stop(exp) if(exp)break;
#define ret(exp) if(exp)return;
#define deb(var) cerr<<#var<<'='<<(var)<<"; "
#define debl(var) cerr<<#var<<'='<<(var)<<";\n"
#define ins insert
#define era erase
#define lb lower_bound
#define inf (long long)(1e9)
template<class T>
bool Min(T &x,T y){return x>y?x=y,1:0;}
template<class T>
bool Max(T &x,T y){return x<y?x=y,1:0;}

int add(int x);
int remove(int x);
void report(int x,int y);

mt19937 eng(random_device{}());
int n,vis[10010],tmp[10010],ins[10010],ord[10010];
void sol(int l,int r,vec<int> w){
    ret(l>r);
    int mid=(l+r)>>1;

    vec<int> v;
    if(l==1&&r==n){
        v=w;
    }else{
        for(auto x:w)tmp[x]=0;
        fill(vis+l,vis+r+1,0);
        iota(ord+l,ord+r+1,l);
        shuffle(ord+l,ord+r+1,eng);
        for(int T=1;T<=4;T++){
            for(int j=l;j<=r;j++){
                int i=ord[j];
                exc(vis[i]);
                if(add(i)>1){
                    remove(i);
                }else{
                    ins[i]=1;
                    vis[i]=1;
                }
            }
            for(auto x:w){
                exc(tmp[x]);
                if(x<=l){
                }else if(x<=r){
                    tmp[x]=1;
                }else{
                    if(add(x)>1)tmp[x]=1;
                    assert(remove(x)<=1);
                }
            }
            for(int i=l;i<=r;i++){
                if(ins[i]){
                    remove(i);
                    ins[i]=0;
                }
            }
            if(!count(vis+l,vis+r+1,0))break;
        }
        for(auto x:w){
            if(tmp[x])v+=x;
        }
    }

    w=v;
    if(l==r){
        for(auto x:w){
            report(l,x);
        }
    }else{
        sol(l,mid,w);
        sol(mid+1,r,w);
    }
}
void solve(int N){
    n=N;
    vec<int> v(n-1);
    iota(all(v),2);
    sol(1,n,v);
}