#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
#define en "\n"
#define cn continue
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<pii>;
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int los(int l, int r) {
return (l + (gen()%(r - l + 1)));
}
vvi g;
void dod(int u, int v) {
if (min(u, v) == -1) return;
g[u].pb(v);
g[v].pb(u);
}
/*int Query(int u, int v, int x) {
cout << "? " << u << " " << v << " " << x << en;
int a;
cin >> a;
return a;
}*/
int jaki(vi &a, int cel) { //jaki z a jest polaczany z v
if (sz(a) == 0) return -1;
if (sz(a) == 1) return a[0];
int v = a[0];
while (true) {
int nowy = -1;
tv(u, g[v]) {
int sr = Query(u, v, cel);
if (sr == u) {
nowy = u;
break;
}
}
if (nowy == -1) return v;
v = nowy;
}
return a[0];
}
int lewy; //z lewej strony
bool cmp(int u, int v) {
int ans = Query(u, v, lewy);
if (ans == u) return true;
return false;
}
void dc(vi a) {
if (sz(a) < 2) return;
if (sz(a) == 2) {
dod(a[0], a[1]);
return;
}
if (sz(a) == 3) {
int sr = Query(a[0], a[1], a[2]);
f(i,0,3) {
if (sr == a[i]) cn;
dod(sr, a[i]);
}
return;
}
int i1 = los(0, sz(a) - 1);
int i2 = los(0, sz(a) - 1);
while (i1 == i2) {
i2 = los(0, sz(a) - 1);
}
int u = a[i1];
int v = a[i2];
vi gr1;
vi gr2;
unordered_map<int, vi> gr3;
tv(ele, a) {
if (ele == u || ele == v) cn;
int sr = Query(u,v,ele);
if (sr == u) {
gr1.pb(ele);
} else if (sr == v) {
gr2.pb(ele);
} else {
gr3[sr].pb(ele);
}
}
gr1.pb(u);
gr2.pb(v);
if (sz(gr3) == 0) {
dod(u, v);
}
dc(gr1);
dc(gr2);
vi gl; //glowne punkty tej sciezki
tv(ele, gr3) {
dc(ele.nd);
gl.pb(ele.st);
}
if (sz(gl) == 0) return;
lewy = u;
sort(all(gl), cmp);
dod(u, gl[0]);
dod(v, gl.back());
f(i, 0, sz(gl) - 1) {
dod(gl[i], gl[i + 1]);
}
}
/*void Bridge(int u, int v) {
if (u > v) {
cout << "blad\n";
}
cout << u << " " << v << en;
}*/
void Solve(int n) {
g = {};
g.resize(n);
vi a(n);
f(i, 0, n) a[i] = i;
dc(a); //divide and conquer
f(i, 0, n) {
tv(u, g[i]) {
if (i < u) {
Bridge(i, u);
}
}
}
}
/*int main() {
Solve(5);
}*/
