#include "meetings.h"
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2000;
int *ej[N], eo[N], eo_[N], ii[N], k, sz[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;
ii[k++] = i;
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;
}
void cd(int r, int i_) {
k = 0; int m = dfs(-1, r), c = r;
for (int h = 0; h < k; h++) {
int i = ii[h];
if (sz[i] >= (m + 1) / 2 && sz[c] > sz[i])
c = i;
}
k = 0, dfs(-1, c);
sort(ej[c], ej[c] + eo[c], [] (int i, int j) { return sz[i] > sz[j]; });
int i = -1;
for (int o = 0; o < eo[c]; o++) {
int j = ej[c][o];
if (used[j])
continue;
if (i == -1) {
i = j;
continue;
}
int c_ = Query(i_, i, j);
if (c_ == c) {
i = -1;
continue;
}
if (c_ != i && c_ != j) {
c_ = Query(i_, i, c);
if (c_ != c) {
detach(i, c), detach(c, i);
if (c_ == i_) {
append(i, i_), append(i_, i);
append(c, i_), append(i_, c);
} else {
append(i, c_), append(c_, i);
append(c, c_), append(c_, c);
append(i_, c_), append(c_, i_);
}
return;
}
c_ = Query(i_, j, c);
detach(j, c), detach(c, j);
if (c_ == i_) {
append(j, i_), append(i_, j);
append(c, i_), append(i_, c);
} else {
append(j, c_), append(c_, j);
append(c, c_), append(c_, c);
append(i_, c_), append(c_, i_);
}
return;
}
used[c] = true;
cd(c_, i_);
return;
}
if (i != -1) {
int c_ = Query(i_, i, c);
if (c_ != c) {
if (c_ != i) {
detach(i, c), detach(c, i);
if (c_ == i_) {
append(i, i_), append(i_, i);
append(c, i_), append(i_, c);
} else {
append(i, c_), append(c_, i);
append(c, c_), append(c_, c);
append(i_, c_), append(c_, i_);
}
return;
}
used[c] = true;
cd(i, i_);
return;
}
}
append(i_, c), append(c, 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;
cd(0, i_);
}
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);
}
}
