#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_set>
//#define DEBUG
using namespace std;
unordered_set<int> gph[2020];
bool chc[2020];
int sz[2020];
bool rchc[2020];
int cen(int x, int p, int s)
{
for(auto y : gph[x]) if(y != p && !chc[y] && sz[y] > s) return cen(y, x, s);
return x;
}
void dfs(int x, int p)
{
sz[x] = 1;
for(auto y : gph[p]) if(y != p && !chc[y])
{
dfs(y, x);
sz[x] += sz[y];
}
}
void Solve(int N)
{
for(int i = 1; i < N; ++i) if(!rchc[i])
{
rchc[i] = true;
for(int j = 0; j < N; ++j) chc[j] = false;
int pr = 0;
while(1)
{
dfs(pr, -1);
int r = cen(pr, -1, sz[pr] / 2);
dfs(r, -1);
chc[r] = true;
#ifdef DEBUG
cout << endl;
cout << "i r" << endl;
cout << i << ' ' << r << endl;
cout << endl;
#endif
vector<int> chd;
for(auto j : gph[r]) if(!chc[j]) chd.push_back(j);
sort(chd.begin(), chd.end(), [](int x, int y){ return sz[x] > sz[y]; });
bool flag = true;
for(auto c : chd)
{
int t = Query(r, c, i);
if(t != r)
{
if(t != c)
{
rchc[t] = true;
gph[r].erase(c);
gph[c].erase(r);
gph[r].insert(t);
gph[t].insert(r);
gph[c].insert(t);
gph[t].insert(c);
gph[i].insert(t);
gph[t].insert(i);
goto A;
}
pr = c;
flag = false;
break;
}
}
if(flag)
{
gph[r].insert(i);
gph[i].insert(r);
goto A;
}
}
A:;
#ifdef DEBUG
cout << endl;
cout << "gph" << endl;
for(int i = 0; i < N; ++i) for(auto j : gph[i]) if(j > i) cout << i << ' ' << j << endl;
cout << endl;
#endif
}
for(int i = 0; i < N; ++i) for(auto j : gph[i]) if(j > i) Bridge(i, j);
}
