#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7;
vector<int>V[LIM], spojna;
int ile[LIM], usun[LIM], odw[LIM], n;
void dodaj_kraw(int a, int b) {
V[a].pb(b);
V[b].pb(a);
}
void usun_kraw(int a, int b) {
rep(i, V[a].size()) if(V[a][i]==b) swap(V[a][i], V[a][V[a].size()-1]);
rep(i, V[b].size()) if(V[b][i]==a) swap(V[b][i], V[b][V[b].size()-1]);
V[a].pop_back();
V[b].pop_back();
}
void DFS(int x, int o) {
spojna.pb(x);
ile[x]=1;
for(auto i : V[x]) if(i!=o && !usun[i]) {
DFS(i, x);
ile[x]+=ile[i];
}
}
int cent(int x) {
spojna.clear();
DFS(x, x);
for(auto i : spojna) {
int ma=spojna.size()-ile[i];
for(auto j : V[i]) if(!usun[j] && ile[j]<ile[i]) ma=max(ma, ile[j]);
if(2*ma<=spojna.size()) return i;
}
return -1;
}
void cd(int x, int p) {
x=cent(x);
spojna.clear();
DFS(x, x);
usun[x]=1;
vector<pair<int,int>>P;
for(auto i : V[x]) if(!usun[i])
P.pb({ile[i], i});
sort(all(P));
reverse(all(P));
for(auto xd : P) {
int i=xd.nd;
int a=Query(x, p, i);
if(a==x) continue;
if(a==i) {
cd(i, p);
return;
}
if(a==p) {
usun_kraw(i, x);
dodaj_kraw(i, p);
dodaj_kraw(p, x);
return;
}
usun_kraw(i, x);
dodaj_kraw(i, a);
dodaj_kraw(a, x);
dodaj_kraw(a, p);
odw[a]=1;
return;
}
dodaj_kraw(x, p);
}
void licz(int x) {
rep(i, n) usun[i]=ile[i]=0;
cd(0, x);
odw[x]=1;
}
void Solve(int _n) {
n=_n;
rep(i, n) if(!odw[i]) licz(i);
rep(i, n) for(auto j : V[i]) if(i<j) Bridge(i, j);
}
