#include "gather.h"
#include<vector>
#include<bits/stdc++.h>
using namespace std;
vector<int> haha[2001];
vector<bool> bruh(2001);
vector<bool> yo(2001,true);
vector<int> st(2001);
vector<int> par(2001);
vector<int> wut(0);
void edge(int x, int y) {
haha[x].push_back(y);
haha[y].push_back(x);
}
void rem(int x, int y) {
bool yeah = false;
for(int i = 0; i < haha[x].size(); i++) {
if(yeah) {
swap(haha[x][i],haha[x][i-1]);
}
if(haha[x][i] == y) {
yeah = true;
}
}
haha[x].pop_back();
yeah = false;
for(int i = 0; i < haha[y].size(); i++) {
if(yeah) {
swap(haha[y][i],haha[y][i-1]);
}
if(haha[y][i] == x) {
yeah = true;
}
}
haha[y].pop_back();
}
void dfs(int a, int t) {
st[a] = 1;
par[a] = t;
wut.push_back(a);
for(int v: haha[a]) {
if(v != t && bruh[v]) {
dfs(v,a);
st[a]+=st[v];
}
}
}
void dude(int a, int z) {
wut.clear();
dfs(a,-1);
if(st[a] == 1) {
haha[a].push_back(z);
haha[z].push_back(a);
return;
}
if(st[a] == 2) {
int y = query(wut[0],wut[1],z);
if(y == wut[0]) {
edge(z,wut[0]);
}
else if(y == wut[1]) {
edge(z,wut[1]);
}
else {
rem(wut[0],wut[1]);
edge(y,wut[0]);
edge(y,wut[1]);
if(y != z) {
yo[y] = false;
edge(y,z);
}
}
return;
}
int c = a;
bool yeah = true;
while(yeah) {
yeah = false;
for(int v: haha[c]) {
if(bruh[v] && st[v] < st[c] & st[v]*2 >= st[a]) {
c = v;
yeah = true;
}
}
}
vector<pair<int,int>> banana(0);
for(int v: haha[c]) {
if(bruh[v]) {
if(st[v] < st[c]) {
banana.push_back({st[v],v});
}
else {
banana.push_back({st[a]-st[c],v});
}
}
}
sort(banana.begin(),banana.end());
reverse(banana.begin(),banana.end());
int x = banana[0].second,y = banana[1].second;
int w = query(x,y,z);
if(w == x || w == y) {
bruh[c] = false;
dude(w,z);
}
else if(w == c) {
bruh[x] = false;
bruh[y] = false;
dude(c,z);
}
else {
if(query(w,c,x) == w) {
rem(c,x);
edge(w,c);
edge(w,x);
if(z != w) {
edge(z,w);
yo[w] = false;
}
}
else {
rem(c,y);
edge(w,c);
edge(w,y);
if(z != w) {
edge(z,w);
yo[w] = false;
}
}
}
}
vector<pair<int,int>> ans(0);
void troll(int a, int t) {
for(int v: haha[a]) {
if(v != t) {
ans.push_back({a,v});
troll(v,a);
}
}
}
std::vector <std::pair <int, int> > solve (int n) {
vector<int> wow(0);
for(int i = 1; i <= n; i++) {
wow.push_back(i);
}
random_shuffle(wow.begin(),wow.end());
haha[wow[0]].push_back(wow[1]);
haha[wow[1]].push_back(wow[0]);
for(int i = 2; i < n; i++) {
if(yo[wow[i]]) {
for(int j = 1; j <= n; j++) {
bruh[j] = 1;
}
dude(wow[0],wow[i]);
}
}
troll(wow[0],-1);
return ans;
}
