#include <bits/stdc++.h>
#include "wheretoreach.h"
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf; 

inline long long read(){
	long long ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 

li fa[200010], id[200010], val[200010];
li q[200010], a[200010], b[200010];

void dfs(li l, li r, li ql, li qr){
    if(l == r){
        for(li i = ql; i <= qr; i++) report(id[q[i]], id[l]);
        return;
    }
    li mid = (l + r) >> 1, p1 = 0, p2 = 0;
    for(li i = l; i <= mid; i++) add(id[i]);
    for(li i = ql; i <= qr; i++){
        if(q[i] <= mid) a[++p1] = q[i];
        else{
            li x = add(id[q[i]]);
            if(x == mid + 1) a[++p1] = q[i];
            else b[++p2] = q[i];
            remove(id[q[i]]);
        }
    }
    for(li i = 1; i <= p1; i++) q[ql + i - 1] = a[i];
    for(li i = 1; i <= p2; i++) q[ql + p1 + i - 1] = b[i];
    if(p2) dfs(mid + 1, r, qr - p2 + 1, qr);
    for(li i = l; i <= mid; i++) remove(id[i]);
    if(p1) dfs(l, mid, ql, ql + p1 - 1);
}

bool cmp(li x, li y){
    return val[x] < val[y];
}

void solve(li n){
    for(li i = 1; i <= n; i++) add(i);
    for(li i = 1; i <= n; i++){
        val[i] = remove(i);
        add(i);
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    for(li i = 2; i <= n; i++) q[i - 1] = i;
    dfs(1, n - 1, 1, n - 1);
}

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);
      |                         ~~~~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc4YvyAl.o: in function `main':
implementer.cpp:(.text.startup+0x14): undefined reference to `solve(int)'
collect2: error: ld returned 1 exit status