#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define pre(x) cout<<fixed; cout.precision(x);
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
int n;
vector<int> g[2010];
int sz[2010];
bool chk[2010];
bool in[2010];
int cnt;
const int MX = 100000;
int q(int u, int v, int w) {
cnt++;
assert(0 <= u && u < n);
assert(0 <= v && v < n);
assert(0 <= w && w < n);
assert(u != v && v != w && w != u);
assert(cnt <= 100000);
return Query(u, v, w);
}
void dfs(int x, int p = 0) {
sz[x] = 1;
for(auto i : g[x]) {
if(i == p || chk[i]) continue;
dfs(i, x);
sz[x] += sz[i];
}
}
int Cen(int x) {
int s = 1, mx = 0, mxi;
for(auto i : g[x]) {
if(chk[i]) continue;
s += sz[i];
if(sz[i] > mx) mx = sz[i], mxi = i;
}
if(mx > s/2) {
sz[x] = s - mx;
return Cen(mxi);
}
return x;
}
pii Find(int x) {
memset(chk, 0, sizeof(chk));
int r = 0;
while(1) {
dfs(r);
r = Cen(r);
//cout << r << "!!!" << endl;
sort(all(g[r]), [](int i, int j) {
return sz[i] > sz[j];
});
for(int i=0; i<g[r].size(); i+=2) {
if(i+1 == g[r].size()) {
if(q(g[r][i], r, x) != r) {
if(chk[g[r][i]]) return mp(r, g[r][i]);
chk[r] = true;
r = g[r][i];
break;
}
}
else if(q(g[r][i], g[r][i+1], x) != r) {
chk[r] = true;
int nr;
if(q(g[r][i], r, x) != r) nr = g[r][i];
else nr = g[r][i+1];
if(chk[nr]) return mp(r, nr);
r = nr;
break;
}
if(i+2 >= g[r].size()) return mp(r, r);
}
}
}
void Solve(int N) {
n = N;
cnt = 0;
for(int i=0; i<n; i++) g[i].clear(), chk[i] = in[i] = false;
g[0].eb(1);
g[1].eb(0);
for(int i=2; i<n; i++) {
if(in[i]) continue;
int u, v;
tie(u, v) = Find(i);
//cout << i << ": " << u << " " << v << "\n";
if(u == v) {
g[u].eb(i);
g[i].eb(u);
continue;
}
int tmp = q(u, v, i);
//cout << tmp << "!\n";
if(tmp == u) {
g[u].eb(i);
g[i].eb(u);
}
else if(tmp == v) {
g[v].eb(i);
g[i].eb(v);
}
else {
if(tmp != i) {
g[tmp].eb(i);
g[i].eb(tmp);
}
g[tmp].eb(u);
g[tmp].eb(v);
for(auto &j : g[u]) if(j == v) j = tmp;
for(auto &j : g[v]) if(j == u) j = tmp;
in[tmp] = true;
}
}
int e = 0;
for(int i=0; i<n; i++) {
for(auto j : g[i]) {
if(i < j) {
e++;
Bridge(i, j);
}
}
}
assert(e == n-1);
}
