#include<utility>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<iostream>
#include<unordered_map>
#include<unordered_map>
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);
void bridge(int i, int j){
//cout << i << " " << j << endl;
Bridge(min(i, j), max(i, j));
}
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;
unordered_map<int, vector<int>> m; vector<int> ch;
m[r], m[v[0]];
for(int cur = v[0], i = 1; i < v.size(); i++){
int x = Query(r, cur, v[i]);
if(x == cur)m[cur = v[i]];
else if(x == v[i])m[x];
else m[x].pb(v[i]);
}
for(auto& i: m){
if(i.ss.size())solve(r = i.ff, i.ss);
ch.pb(i.ff);
}
sort(all(ch), [](int a, int b) {
if(!a)return true; if(!b)return false;
return a != b && Query(0, a, b) == a;
});
for(int i = 1; i < ch.size(); i++)bridge(ch[i-1], ch[i]);
}
void Solve(int N){
vector<int> v(N-1);
iota(all(v), 1);
solve(0, v);
}
