#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
void solve(vector<int> vec)
{
if(vec.size() == 1)
return;
else if(vec.size() == 2)
{
if(vec[0] > vec[1])
swap(vec[0], vec[1]);
Bridge(vec[0], vec[1]);
return;
}
shuffle(vec.begin(), vec.end(), rng);
int x = vec[0], y = vec[1];
map<int, bool> used;
used[x] = used[y] = 1;
vector<int> a = {x}, b = {y};
for(int i = 2; i < vec.size(); i++)
{
if(used[vec[i]])
continue;
used[vec[i]] = 1;
int z = Query(x, y, vec[i]);
if(z == x)
a.push_back(vec[i]);
else if(z == y)
b.push_back(vec[i]);
else if(z == vec[i])
{
if(a.size() > b.size())
{
y = vec[i];
b.push_back(vec[i]);
}
else
{
x = vec[i];
a.push_back(vec[i]);
}
}
else
{
used[z] = 1;
if(a.size() > b.size())
{
y = z;
b.push_back(z);
b.push_back(vec[i]);
}
else
{
x = z;
a.push_back(z);
a.push_back(vec[i]);
}
}
}
Bridge(min(x, y), max(x, y));
solve(a);
solve(b);
}
void Solve(int N)
{
vector<int> vec;
for(int i = 0; i < N; i++)
vec.push_back(i);
solve(vec);
}
