#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,ord[10010],ed[10010];
bool used[10010],in[10010];

void deter(vec<pii> w,int l,int r){
    for(auto x:w)ed[x.x]=0;
    fill(used+l,used+r+1,0);
    for(int T=1;;T++){
        for(int i=l;i<=r;i++){
            exc(used[i]);
            if(add(ord[i])>1){
                remove(ord[i]);
            }else{
                in[i]=used[i]=1;
            }
        }
        for(auto x:w){
            if(x.x>r){
                ed[x.x]+=add(ord[x.x])-1;
                remove(x.x);
            }
        }
        for(int i=l;i<=r;i++){
            if(in[i]){
                remove(ord[i]);
                in[i]=0;
            }
        }
        if(!count(used+l,used+r+1,0))break;
    }
}
void sol(int l,int r,vec<pii> w){
    ret(l>r);
    if(l==r){
        deter(l,r,w);
        for(auto x:w){
            assert(ed[x.x]<=1);
        }
        for(auto x:w){
            // if(x.y>=2){
                // assert(0);
            // }
            // assert(x.y<=1);
            if(x.y==1)
            report(ord[l],ord[x.x]);
        }
    }else{
        int mid=(l+r)>>1;
        deter(w,l,mid);
        vec<pii> ls,rs;
        for(auto t:w){
            int x,y;
            tie(x,y)=t;

            if(x<=mid){
                ls+={x,0};
            }
            if(x>mid&&x<=r){
                rs+={x,0};
            }
            if(x>mid&&ed[x]){
                ls+={x,ed[x]};
            }
            // if(x>r){
            //     assert(y);
            // }
            if(x>r&&ed[x]<y){
                rs+={x,y-ed[x]};
            }
        }
        sol(l,mid,ls);
        sol(mid+1,r,rs);
    }
}
int wgt[10010];
void solve(int N){
    n=N;

    for(int i=1;i<=n;i++){
        add(i);
    }
    for(int i=1;i<=n;i++){
        wgt[i]=remove(i);
        add(i);
    }
    for(int i=1;i<=n;i++){
        remove(i);
    }
    iota(ord+1,ord+n+1,1);
    sort(ord+1,ord+n+1,[&](int x,int y){
        return wgt[x]<wgt[y];
    });
    vec<pii> v;
    for(int i=2;i<=n;i++){
        v+={i,0};
    }
    sol(1,n,v);
}

implementer.cpp: In function ‘void Interactor::init()’:
implementer.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |                 scanf("%d",&n);
      |                 ~~~~~^~~~~~~~~
implementer.cpp:30:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |                         scanf("%d%d",&x,&y); v[x].push_back(y),v[y].push_back(x);
      |                         ~~~~~^~~~~~~~~~~~~~
answer.code: In function ‘void sol(int, int, std::vector<std::pair<int, int> >)’:
answer.code:69:15: error: could not convert ‘l’ from ‘int’ to ‘std::vector<std::pair<int, int> >’
   69 |         deter(l,r,w);
      |               ^
      |               |
      |               int