#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n;
map<array<int, 3>, int>cache;
int ask(int u, int v, int w){
if(u > v){
swap(u, v);
}
if(v > w){
swap(v, w);
}
if(u > v){
swap(u, v);
}
auto it = cache.find({u, v, w});
if(it != cache.end()){
return it->second;
}
return cache[{u, v, w}] = Query(u, v, w);
}
namespace sub12{
bool check(int u, int v){
for(int w = 0; w < n; w++){
if(w != u && w != v){
int x = ask(u, v, w);
if(x != u && x != v){
return false;
}
}
}
return true;
}
void solve(){
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(check(i, j)){
Bridge(i, j);
}
}
}
}
}
namespace sub3{
const int lim = 305;
void play(vector<int>p){
if(p.size() == 1){
return;
}
shuffle(p.begin(), p.end(), rng);
int root = p[0];
bitset<lim>vis;
vis.reset();
while(true){
int child = -1;
for(int i = 1; i < p.size(); i++){
if(!vis[p[i]]){
child = p[i];
break;
}
}
if(child == -1){
break;
}
vector<int>np(1, child);
vis[child] = true;
for(int i = 1; i < p.size(); i++){
if(!vis[p[i]]){
int x = ask(root, child, p[i]);
if(x != root){
np.push_back(child = x);
np.push_back(p[i]);
vis[x] = vis[p[i]] = true;
}
}
}
Bridge(min(root, child), max(root, child));
sort(np.begin(), np.end());
np.resize(unique(np.begin(), np.end()) - np.begin());
play(np);
}
}
void solve(){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
play(p);
}
}
namespace sub4{
const int lim = 2e3 + 5;
set<int>g[lim];
int siz[lim];
void add_edge(int u, int v){
g[u].insert(v);
g[v].insert(u);
}
void remove_edge(int u, int v){
g[u].erase(v);
g[v].erase(u);
}
bitset<lim>vis;
void dfs(int s, int p){
siz[s] = 1;
for(const int& d : g[s]){
if(d != p && !vis[d]){
dfs(d, s);
siz[s] += siz[d];
}
}
}
void centroid_dec(int s, const int iv){
dfs(s, -1);
int N = siz[s], p = -1;
while(true){
bool flag = true;
for(const int& d : g[s]){
if(d != p && !vis[d] && siz[d] > (N >> 1)){
p = s;
s = d;
flag = false;
break;
}
}
if(flag){
break;
}
}
dfs(s, -1);
vis[s] = true;
vector<int>cd;
for(const int& d : g[s]){
if(!vis[d]){
cd.push_back(d);
}
}
sort(cd.begin(), cd.end(), [&] (int i, int j){
return siz[i] < siz[j];
});
while(cd.size() > 1){
int d1 = cd.back(), d2 = cd[int(cd.size()) - 2];
cd.pop_back();
cd.pop_back();
int x = ask(iv, d1, d2);
if(x != s){
if(x == d1 || x == d2){
centroid_dec(x, iv);
}
else if(x == iv){
add_edge(s, iv);
if(ask(iv, s, d1) == iv){
remove_edge(s, d1);
add_edge(d1, x);
}
else{
remove_edge(s, d2);
add_edge(d2, x);
}
}
else{
add_edge(x, iv);
add_edge(s, x);
if(ask(s, d1, iv) == x){
remove_edge(s, d1);
add_edge(x, d1);
}
else{
remove_edge(s, d2);
add_edge(x, d2);
}
}
return;
}
}
if(!cd.empty()){
int x = ask(iv, s, cd[0]);
if(x != s){
if(x == cd[0]){
centroid_dec(x, iv);
}
else if(x == iv){
add_edge(s, iv);
remove_edge(s, cd[0]);
add_edge(cd[0], x);
}
else{
add_edge(x, iv);
add_edge(s, x);
remove_edge(s, cd[0]);
add_edge(x, cd[0]);
}
return;
}
}
add_edge(s, iv);
}
void solve(){
add_edge(0, 1);
for(int i = 2; i < n; i++){
if(g[i].empty()){
vis.reset();
centroid_dec(0, i);
}
}
for(int i = 0; i < n; i++){
for(const int& j : g[i]){
if(j > i){
break;
}
Bridge(j, i);
}
}
}
}
void Solve(int _n){
if((n = _n) <= 50){
sub12::solve();
}
else if(n <= 300){
sub3::solve();
}
else{
sub4::solve();
}
}
