#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define query Query
#define answer Bridge
#define pb push_back
const int lim=2100;
unordered_set<int>v[lim];
vector<int>ch;
int dfs(int node,int par,int targ){
if(node==targ){
ch.clear();
ch.pb(node);
return 1;
}
for(int j:v[node]){
if(j==par)continue;
if(dfs(j,node,targ)){
ch.pb(node);
return 1;
}
}
return 0;
}
int gonna[lim];
void killall(int node,int par,int targ){
if(node==targ)return;
gonna[node]=0;
for(int j:v[node]){
if(j==par)continue;
killall(j,node,targ);
}
}
void Solve(int n){
v[0].insert(1);
v[1].insert(0);
int vis[n]{};
vis[0]=vis[1]=1;
for(int i=2;i<n;i++){
if(vis[i])continue;
for(int j=0;j<n;j++)gonna[j]=1;
while(!vis[i]){
int cnt=0,dude=0;
for(int j=0;j<n;j++){
if(vis[j]&&gonna[j]){
// cerr<<j<<" active\n";
cnt++;
dude=j;
}
}
if(cnt==1){
// cerr<<"ma dude "<<i<<' '<<dude<<'\n';
vis[i]=1;
v[i].insert(dude);
v[dude].insert(i);
break;
}
vector<int>leafs;
for(int j=0;j<n;j++){
if(vis[j]&&gonna[j]){
int cc=0;
for(int k:v[j]){
cc+=vis[k]&&gonna[k];
if(cc==2)break;
}
if(cc==1){
leafs.pb(j);
if(leafs.size()==2)break;
}
}
}
// cerr<<cnt<<' '<<leafs.size()<<'\n';
assert(leafs.size()==2);
// cerr<<leafs[0]<<' '<<leafs[1]<<' '<<i<<'\n';
int res=query(leafs[0],leafs[1],i);
// cerr<<"asked "<<leafs[0]<<' '<<leafs[1]<<' '<<i<<' '<<res<<'\n';
if(!vis[res]){
// cerr<<"missing "<<leafs[0]<<' '<<leafs[1]<<' '<<res<<'\n';
dfs(leafs[0],-1,leafs[1]);
// cerr<<"ch : ";
// for(int jj:ch)cerr<<jj<<' ';
// cerr<<'\n';
// assert(ch.size()>=2);
// assert(ch[0]==leafs[1]&&ch.back()==leafs[0]);
int l=1,r=ch.size()-2,ans=ch.size()-1;
while(l<=r){
int mid=l+r>>1;
// cerr<<ch[mid]<<' '<<ch.back()<<' '<<res<<'\n';
int cur=query(ch[mid],ch.back(),res);
if(cur==res){
l=mid+1;
}else{
ans=mid;
r=mid-1;
}
}
// cerr<<"here\n";
// cerr<<ch[ans]<<' '<<ch[ans-1]<<' '<<res<<" inserted\n";
// assert(v[ch[ans]].count(ch[ans-1]));
v[ch[ans]].erase(ch[ans-1]);
v[ch[ans-1]].erase(ch[ans]);
v[ch[ans]].insert(res);
v[res].insert(ch[ans]);
v[ch[ans-1]].insert(res);
v[res].insert(ch[ans-1]);
vis[res]=1;
}
killall(leafs[0],-1,res);
killall(leafs[1],-1,res);
gonna[res]=1;
}
// for(int i=0;i<n;i++){
// for(int j:v[i]){
// cerr<<i<<' '<<j<<'\n';
// }
// }cerr<<'\n';
}
for(int i=0;i<n;i++){
for(int j:v[i]){
// cerr<<i<<' '<<j<<'\n';
if(i<j){
answer(i,j);
}
}
}
}
// void Solve(int N) {
// int x = Query(0, 1, 2);
// for (int u = 0; u < N - 1; ++u) {
// Bridge(u, u + 1);
// }
// }
