// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using vi = V<int>;
const int nax = 2005;
set<int> adj[nax];
int sub[nax], dead[nax];
void gen(int u, int p) {
sub[u] = 1;
for(auto& v : adj[u]) if (v != p && !dead[v]) {
gen(v, u);
sub[u] += sub[v];
}
}
int find(int u, int p, int n) {
for(auto& v : adj[u]) if (v != p && !dead[v]) {
if (2 * sub[v] > n) return find(v, u, n);
}
return u;
}
void rem(int u, int v) {
adj[u].erase(v);
adj[v].erase(u);
// cout << "REM: " << u << " " << v << endl;
}
void add(int u, int v) {
// cout << "ADD: " << u << " " << v << endl;
adj[u].insert(v);
adj[v].insert(u);
}
void place(int x) {
memset(sub, 0, sizeof sub);
memset(dead, 0, sizeof sub);
int r = 0;
while(1) {
gen(r, -1);
// cout << x << " => " << sub[r] << endl;
int u = find(r, -1, sub[r]);
vi ADJ; for(auto& v : adj[u]) if (!dead[v]) {
ADJ.pb(v);
}
if (sz(ADJ) == 0) {
add(u, x);
return;
} else if (sz(ADJ) == 1) {
int v = ADJ[0];
// cout << "Q1: " << u << " " << v << " " << x << endl;
int X = Query(u, v, x);
if (X == u) {
dead[v] = 1;
r = u;
} else if (X == v) {
dead[u] = 1;
r = v;
} else {
rem(u, v); add(u, X); add(X, v);
if (X != x) add(X, x);
return;
}
} else {
for(int i = 0; i < sz(ADJ); i += 2) {
int a = ADJ[i], b = ADJ[i + 1];
if (i == sz(ADJ) - 1) {
r = u;
break;
}
// cout << "Q2: " << a << " " << b << " " << x << endl;
int R = Query(a, b, x);
if (R == a || R == b) {
dead[u] = 1;
r = R;
break;
} else if (R == u) {
dead[a] = dead[b] = 1;
r = u;
} else {
// In the edge between (a, u) or (b, u)
// cout << "Q3: " << a << " " << u << " " << x << endl;
{
int X = Query(a, u, x);
if (X != u) {
// X in between (a, u)
rem(a, u); add(a, X); add(X, u);
if (X != x) add(X, x);
return;
}
}
// cout << "Q3: " << a << " " << u << " " << x << endl;
{
int X = Query(b, u, x);
if (X != u) {
// x in between (b, u)
rem(b, u); add(b, X); add(X, u);
if (X != x) add(X, x);
return;
}
}
assert(false);
}
}
}
}
}
void Solve(int N) {
adj[0] = {1}; adj[1] = {0};
for(int i = 2; i < N; i++) {
if (!sz(adj[i])) place(i);
// for(int x = 0; x < N; x++) for(auto& y : adj[x]) {
// if (x < y) {
// cout << "E: " << x << " " << y << endl;
// }
// }
// cout << endl;
}
for(int x = 0; x < N; x++) for(auto& y : adj[x]) {
if (x < y) {
// cout << "E: " << x << " " << y << endl;
Bridge(x, y);
}
}
}
