#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]){
cnt++;
dude=j;
}
}
if(cnt==1){
vis[i]=1;
v[i].insert(dude);
v[dude].insert(i);
break;
}
vector<int>leafs;
for(int j=0;j<n;j++){
if(gonna[j]&&v[j].size()==1){
leafs.pb(j);
if(leafs.size()==2)break;
}
}
int res=query(leafs[0],leafs[1],i);
if(!vis[res]){
dfs(leafs[0],-1,leafs[1]);
int l=2,r=ch.size()-1,ans=1;
while(l<=r){
int mid=l+r>>1;
int cur=query(ch[mid],ch.back(),res);
if(cur==res){
r=mid-1;
}else{
ans=mid;
l=mid+1;
}
}
v[ch[ans]].erase(ch[ans-1]);
v[ch[ans-1]].erase(ch[ans]);
v[ch[ans]].insert(res);
v[ch[ans-1]].insert(res);
vis[res]=1;
}
killall(leafs[0],-1,res);
killall(leafs[1],-1,res);
}
}
for(int i=0;i<n;i++){
for(int j:v[i]){
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);
// }
// }
