#include "meetings.h"
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2000;
int *ej[N], eo[N], eo_[N], ii[N], k, pp[N], sz[N], kk[N];
bool used[N];
void append(int i, int j) {
int o = eo[i]++;
if (o == eo_[i])
if (!o)
ej[i] = (int *) malloc(sizeof *ej[i]), eo_[i] = 1;
else if (!(o & o - 1))
ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]), eo_[i] <<= 1;
ej[i][o] = j;
}
void detach(int i, int j) {
for (int o = 0; o < eo[i]; o++)
if (ej[i][o] == j) {
for (eo[i]--; o < eo[i]; o++)
ej[i][o] = ej[i][o + 1];
break;
}
}
int dfs(int p, int i) {
if (used[i])
return 0;
pp[ii[k++] = i] = p;
int s = 1;
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o];
if (j != p)
s += dfs(i, j);
}
return sz[i] = s;
}
bool cd(int r, int i_) {
k = 0; int m = dfs(-1, r), s = r;
for (int h = 0; h < k; h++) {
int i = ii[h];
if (abs(sz[s] - (m - sz[s])) > abs(sz[i] - (m - sz[i])))
s = i;
}
if (s == r)
return false;
int t = pp[s], c = Query(i_, s, t);
if (c != s && c != t) {
detach(s, t), detach(t, s);
if (c == i_) {
append(s, i_), append(i_, s);
append(t, i_), append(i_, t);
} else {
append(s, c), append(c, s);
append(t, c), append(c, t);
append(i_, c), append(c, i_);
}
return true;
}
kk[c]++;
if (c == s) {
used[t] = true;
return cd(s, i_);
} else {
used[s] = true;
return cd(t, i_);
}
}
void Solve(int n) {
append(0, 1), append(1, 0);
for (int i_ = 2; i_ < n; i_++) {
if (eo[i_])
continue;
for (int i = 0; i < n; i++)
used[i] = false, kk[i] = 0;
if (cd(0, i_))
continue;
for (int c = 0; c < n; c++)
if (kk[c] && kk[c] == eo[c]) {
append(i_, c), append(c, i_);
break;
}
}
for (int i = 0; i < n; i++)
for (int o = 0; o < eo[i]; o++) {
int j = ej[i][o];
if (i < j)
Bridge(i, j);
}
}
