#include<utility>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<iostream>
#include<map>
#include<set>
using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
_x = 0;
int _tmp = 1; char _tc = getchar();
while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
if(_tc == '-') _tc = getchar(), _tmp = -1;
while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
_x *= _tmp;
}
inline void output(int _x) {
char _buff[20]; int _f = 0;
if(_x == 0)putchar('0');
while(_x > 0)
{
_buff[_f++] = _x%10+'0';
_x /= 10;
}
for(_f-=1; _f >= 0; _f--)
putchar(_buff[_f]);
putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
s<<"[";
for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
s<<"]";
return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
return _out(s,c.begin(),c.end());
}
#ifdef erd1
#define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
#define pprint(x)
#endif
// code starts here
int Query(int, int, int);
void Bridge(int, int);
int query(int a, int b, int c){
static int x = 0;
if(++x > 40000)exit(0);
return Query(a, b, c);
}
inline void bridge(int i, int j){
//cout << i << " " << j << endl;
Bridge(min(i, j), max(i, j));
}
int curr = 0, biggest = -1;
struct comp {
bool operator()(int a, int b){
if(a == b)return false;
if(a == curr)return true;
if(b == curr)return false;
if(a == biggest)return false;
if(b == biggest)return true;
return query(curr, a, b) == a;
}
};
inline void insert(set<int, comp>& s, int a){
biggest = a, s.insert(a), biggest = -1;
}
void solve(int r, vector<int>& v){
//cout << r << v << endl;
if(v.size() == 1) return bridge(r, v[0]);
if(v.size() <= 1) return;
curr = r;
map<int, vector<int>> m; set<int, comp> ch;
m[r], m[v[0]];
ch.insert(r); insert(ch, v[0]);
for(int cur = v[0], i = 1; i < v.size(); i++){
int x = query(r, cur, v[i]);
if(x == cur){
if(m.find(cur) == m.end())
m[cur], insert(ch, cur);
cur = v[i];
} else {
if(m.find(x) == m.end())
m[x], ch.insert(x);
if(x != v[i])
m[x].pb(v[i]);
}
if(i == v.size()-1)
if(m.find(cur) == m.end())
m[cur], insert(ch, cur);
}
for(auto& i: m)
if(i.ss.size())solve(r = i.ff, i.ss);
for(auto it1 = ch.begin(), it2 = next(it1); it2 != ch.end(); it1++, it2++)
bridge(*it1, *it2);
}
void Solve(int N){
vector<int> v(N);
srand((intptr_t)(void*)new int());
iota(all(v), 0);
random_shuffle(all(v));
int x = v.back(); v.pop_back();
solve(x, v);
}
