#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3;
const int mod = 998244853;
const int inf = 2e9;
int rng = 123456;
int genrandom(){
rng = (1ll*rng*101 + 29)%mod;
return rng;
}
vector <int> e[N];
vector <int> nr;
int bad[N];
bool vis[N];
int sub[N];
void addedge(int x,int u,int w){
vis[x] = 1;
nr.push_back(x);
//cout<<"addedge:"<<x<<' '<<u<<' '<<w<<'\n';
if(w == -1){
e[u].push_back(x);
e[x].push_back(u);
return;
}else{
for(int i = 0;i < e[u].size();i++){
if(e[u][i] == w){
swap(e[u][i],e[u].back());
e[u].pop_back();
break;
}
}
swap(u,w);
for(int i = 0;i < e[u].size();i++){
if(e[u][i] == w){
swap(e[u][i],e[u].back());
e[u].pop_back();
break;
}
}
e[u].push_back(x);
e[x].push_back(u);
e[x].push_back(w);
e[w].push_back(x);
}
}
void cendecomp(int x, int node = nr[0]){
int sz = 0;
int cen = -1,cennr = inf;
auto dfs = [&](auto self, int node, int p) -> void{
sz++;
sub[node] = 1;
for(auto i:e[node]){
if(i == p || bad[i])continue;
self(self, i, node);
sub[node]+=sub[i];
}
};
auto dfs2 = [&](auto self, int node, int p) -> void{
int mx = -1;
for(auto i:e[node]){
if(i == p || bad[i])continue;
self(self, i, node);
if(mx < sub[i]){
mx = sub[i];
}
}
if(mx < sz - sub[node]){
mx = sz - sub[node];
}
if(cennr > mx){
cennr = mx;
cen = node;
}
};
sz = 0;
dfs(dfs, node, -1);
dfs2(dfs2, node, -1);
dfs(dfs, cen, -1);
vector <int> cands;
for(auto i:e[cen]){
if(bad[i])continue;
cands.push_back(i);
}
sort(cands.begin(),cands.end(),[&](int a, int b){
return sub[a] > sub[b];
});
if(cands.empty()){
///fuck it i give up
addedge(x,cen,-1);
return;
}/*cout<<"centroid:"<<cen<<'\n';
for(int i = 0;i < (int)cands.size();i++){
cout<<cands[i]<<' ';
}
cout<<'\n';*/
bad[cen] = 1;
for(int i = 0;i < (int)cands.size() - 1;i+=2){
int p = Query(cands[i],cands[i + 1],x);
if(p == cands[i] || p == cands[i + 1]){
cendecomp(x, p);
return;
}else if(p == x){
///what the fuck
int q = Query(cands[i],cen,x);
if(q == x){
addedge(x,cands[i],cen);
}else if(q == cen){
addedge(x,cands[i + 1],cen);
}else{
///fcuk
assert(0);
}
return;
}else if(p != cen){
assert(0);
return;
}
}
if(0 && cands.size()%2 == 0){
addedge(x,cen,-1);
}else{
int p = Query(cands[(int)cands.size() - 1],cen,x);
if(p == x){
addedge(x,cands[(int)cands.size() - 1],cen);
}else if(p == cands[(int)cands.size() - 1]){
cendecomp(x, cands[(int)cands.size() - 1]);
}else if(p == cen){
addedge(x,cen,-1);
}else{
addedge(p, cands[(int)cands.size() - 1], cen);
}
}
}
void add(int x){
if(nr.empty()){
nr.push_back(x);
vis[x] = 1;
return;
}else if(nr.size() == 1){
addedge(x,nr[0],-1);
return;
}
//cout<<"add:"<<x<<'\n';
for(int i = 0;i < nr.size();i++){
//cout<<nr[i]<<' ';
bad[nr[i]] = 0;
}
//cout<<'\n';
cendecomp(x);
}
void Solve(int n){
while(nr.size() < n){
int id = genrandom()%n;
//cout<<genrandom()%n<<'\n';
if(!vis[id]){
add(id);
}
}
for(int i = 0;i < n;i++){
for(auto j:e[i]){
if(i < j){
//cout<<i<<' '<<j<<'\n';
Bridge(i, j);
}
}
}
}
/**
5
0 1
0 2
1 3
1 4
**/
