#include "icc.h"
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
int dsu[111];
vector<int> dset[111];
set<int>rts;
int find(int x){return(dsu[x] == x ? x : dsu[x] = find(dsu[x]));}
int CNT = 0;
void merge(int a,int b){
int fa = find(a),fb = find(b);
if(dset[fb].size() > dset[fa].size()) swap(fa,fb);
for(auto x : dset[fb]) dset[fa].push_back(x);
rts.erase(fb);
dsu[fb] = fa;
}
vector<vector<int>> split(vector<int>f,vector<int>s){
vector<int>f1 = {},s1 = {};
int szf = f.size(),szs = s.size();
while(f.size() > f1.size()){
int prev = -1;
while(f.size() && (prev == -1 || find(f.back()) == prev)){
prev = find(f.back());
f1.push_back(f.back());
f.pop_back();
szf--;
}
}
while(s.size() > s1.size()){
int prev = -1;
while(s.size() && (prev == -1 || find(s.back()) == prev)){
prev = find(s.back());
s1.push_back(s.back());
s.pop_back();
}
}
if(!f.size()){
int prev = -1;
while(f1.size() && (prev == -1 || find(f1.back()) == prev)){
prev = find(f1.back());
f.push_back(f1.back());
f1.pop_back();
}
}
if(!s.size()){
int prev = -1;
while(s1.size() && (prev == -1 || find(s1.back()) == prev)){
prev = find(s1.back());
s.push_back(s1.back());
s1.pop_back();
}
}
swap(f1,s);
// cout<<"SPLIT OPERATION\n";
// cout<<"F: ";
// for(auto x : f) cout<<x<<' ';
// cout<<'\n';
// cout<<"S: ";
// for(auto x : s) cout<<x<<' ';
// cout<<'\n';
// cout<<"F1: ";
// for(auto x : f1) cout<<x<<' ';
// cout<<'\n';
// cout<<"S1: ";
// for(auto x : s1) cout<<x<<' ';
// cout<<'\n';
// if(f1.size() + f.size() + s.size() + s1.size() == 0) exit(0);
return {f,f1,s,s1};
}
int F[111],S[111];
vector<vector<int>>f,s;
bool spl = 1;
bool qmap(){
// if(CNT == 40) exit(0);
// CNT++;
// if(spl) cout<<"SPLIT\n";
// else cout<<"FIND\n";
int fsz = 0,ssz = 0;
int i = 0,id = 0;
// cout<<"F: ";
while(id < f.size()){
for(auto x : f[id]){
F[i] = x;
// cout<<F[i]<<' ';
i++;
}
fsz += f[id].size();
id++;
}
// cout<<'\n';
i = 0;
id = 0;
// cout<<"S: ";
while(id < s.size()){
for(auto x : s[id]){
S[i] = x;
// cout<<S[i]<<' ';
i++;
}
ssz += s[id].size();
id++;
}
// cout<<'\n';
return query(fsz,ssz,F,S);
}
bool cmp(int a,int b){
return find(a) < find(b);
}
void run(int N){
for(int i = 1;i <= N;i++){
rts.insert(i);
dsu[i] = i;
dset[i] = {i};
}
int test = N - 1;
while(test--){
spl = 1;
f.clear();
s.clear();
f.push_back({});
s.push_back({});
for(auto x : rts){
for(auto el : dset[x]){
f[0].push_back(el);
}
}
// for(auto x : f[0]) cout<<x<<' ';
while(f[0].size() > s[0].size()){
int prev = -1;
while(f[0].size() && (prev == -1 || find(f[0].back()) == prev)){
prev = find(f[0].back());
s[0].push_back(f[0].back());
f[0].pop_back();
}
}
// cout<<"INITSPLIT\n";
// cout<<"F: ";
// for(auto x : f[0]) cout<<x<<' ';
// cout<<'\n';
// cout<<"S: ";
// for(auto x : s[0]) cout<<x<<' ';
// cout<<'\n';
bool found = qmap();
while(!found){
vector<vector<int>>ft,st;
for(int i = 0;i < f.size();i++){
auto x = split(f[i],s[i]);
ft.push_back(x[0]);
ft.push_back(x[1]);
st.push_back(x[2]);
st.push_back(x[3]);
}
f.clear();
s.clear();
for(auto x : ft){
f.push_back(x);
}
for(auto x : st){
s.push_back(x);
}
// cout<<f.size();
// for(auto x : f){
// for(auto el : x) cout<<el<<' ';
// }
// cout<<'\n';
found = qmap();
}
spl = 0;
int l = -1,r = -1;
while(1){
int szf = 0,szs = 0;
vector<vector<int>>fh,sh;
for(int i = 0;i < f.size();i++){
if(i < f.size() / 2) fh.push_back(f[i]);
else sh.push_back(f[i]);
}
swap(fh,f);
vector<vector<int>>sfh,ssh;
for(int i = 0;i < s.size();i++){
if(i < s.size() / 2) sfh.push_back(s[i]);
else ssh.push_back(s[i]);
}
swap(sfh,s);
found = qmap();
if(!found) swap(sh,f);
if(!found) swap(ssh,s);
l = 0,r = 0;
for(auto x : f){
for(auto el : x){
l++;
break;
}
}
for(auto x : s){
for(auto el : x){
r++;
break;
}
}
if(l == 1 && r == 1) break;
// if(found) break;
}
// cout<<"F: ";
// for(auto x : f[0]) cout<<x<<' ';
// cout<<'\n';
// cout<<"S: ";
// for(auto x : s[0]) cout<<x<<' ';
// cout<<'\n';
while(f[0].size() > 1){
vector<int>fh,sh;
for(int i = 0;i < f[0].size();i++){
if(i < f[0].size() / 2) fh.push_back(f[0][i]);
else sh.push_back(f[0][i]);
}
swap(fh,f[0]);
found = qmap();
if(!found) swap(sh,f[0]);
}
while(s[0].size() > 1){
vector<int>fh,sh;
for(int i = 0;i < s[0].size();i++){
if(i < s[0].size() / 2) fh.push_back(s[0][i]);
else sh.push_back(s[0][i]);
}
swap(fh,s[0]);
found = qmap();
if(!found) swap(sh,s[0]);
}
merge(f[0][0],s[0][0]);
// cout<<"FOUND: "<<f[0][0]<<' '<<s[0][0]<<'\n';
setRoad(f[0][0],s[0][0]);
}
}
