#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], czyw[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(b); ed[c].pb(a);
}
void Ins(int nw, int n)
{
if(czyw[nw]) return;
int il = 0, s = 1;
for(int i = 0; i < n; ++i)
{
if(czyw[i]) ++il;
vis[i] = 0;
}
//cerr << "Ins: " << nw << "\n";
czyw[nw] = 1;
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;
//bool xd = 0;
for(int i = 0; i < (int)akt.size(); ++i)
{
int a = Query(v, akt[i], nw);
if(a == v) continue;
if(a == nw)
{
//cerr << "A: " << v << " " << akt[i] << "\n";
Insert(v, akt[i], nw);
//if(xd)
//{ed[v].pop_back(); ed[nw].pop_back();}
//cerr << ed[akt[i]].size() << " " << ed[akt[i]][0] << "\n";
return;
}
if(a == akt[i])
{
//cerr << "B: " << v << " " << akt[i] << "\n";
il = siz[akt[i]];
s = akt[i];
break;
}
//if(czyw[a]) continue;
//cerr << "C: " << v << " " << a << " " << akt[i] << " " << nw << "\n";
erase(ed[akt[i]], v); erase(ed[v], akt[i]);
ed[v].pb(a); ed[a].pb(v);
ed[a].pb(nw); ed[nw].pb(a);
ed[a].pb(akt[i]); ed[akt[i]].pb(a);
czyw[a] = 1;
return;
}
if(s == -1)
{
//cerr << "D: " << v << " " << akt.size() << " " << ed[v].size() << "\n";
ed[v].pb(nw);
ed[nw].pb(v);
return;
}
}
}
void Solve(int _N)
{
int n = _N;
czyw[0] = 1; czyw[1] = 1;
if(n == 1) return;
ed[0].pb(1); ed[1].pb(0);
for(int i = 2; i < n; ++i)
Ins(i, n);
/*for(int i = 0; i < n; ++i)
for(int j = 0; j < (int)ed[i].size(); ++j)
if(ed[i][j] > i)
cerr << "Ans: " << i << " " << ed[i][j] << "\n";*/
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]);
}
