#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 2'007;
bool vis[N];
int siz[N];
vector<int> ed[N];
int cen;
bool Cp(int a, int b)
{
return (siz[a] > siz[b]);
}
void DFS(int v, int il)
{
vis[v] = 1; siz[v] = 1;
bool czy = 1;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(vis[ed[v][i]]) continue;
DFS(ed[v][i], il);
if(siz[ed[v][i]] > il / 2) czy = 0;
siz[v] += siz[ed[v][i]];
}
if(il - siz[v] > il / 2) czy = 0;
if(czy) cen = v;
vis[v] = 0;
}
void Insert(int a, int b, int c)
{
erase(ed[a], b); erase(ed[b], a);
ed[a].pb(c); ed[b].pb(c);
ed[c].pb(a); ed[c].pb(b);
}
void Ins(int nw, int n)
{
int il = n, s = 1;
for(int i = 0; i < n; ++i) vis[i] = 0;
while(true)
{
DFS(s, il);
s = -1;
int v = cen;
vector<int> akt;
for(int i = 0; i < (int)ed[v].size(); ++i)
if(!vis[ed[v][i]]) akt.pb(ed[v][i]);
sort(akt.begin(), akt.end(), Cp);
vis[v] = 1;
for(int i = 0; i < (int)akt.size(); ++i)
{
int a = Query(v, akt[i], nw);
if(a == nw)
{
Insert(v, akt[i], nw);
return;
}
if(a == akt[i])
{
il = siz[akt[i]];
s = akt[i];
break;
}
}
if(s == -1)
{
ed[v].pb(nw);
ed[nw].pb(v);
return;
}
}
}
void Solve(int _N)
{
int n = _N;
if(n == 1) return;
ed[0].pb(1); ed[1].pb(0);
for(int i = 2; i < n; ++i)
Ins(i, i);
for(int i = 0; i < n; ++i)
for(int j = 0; j < (int)ed[i].size(); ++j)
if(ed[i][j] > i)
Bridge(i, ed[i][j]);
}
