#include"path.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,N;
int frp[100005],p[100005],buc[100005],inq[100005];
mt19937 rnd(1);
vector <int> sta,occ[100005];
void solve(int rt){
	++N;
	rep(i,1,N) occ[i].clear();
	rep(u,1,n) if(frp[u]) occ[frp[u]].eb(u);
//	cerr << "choose " << rt << endl;
	int temp;
	sta.clear();
	rep(u,1,n){
		inq[u] = 0;
		if(u == rt || frp[u]) continue;
		if(sta.empty()){
			inq[u] = 1;
			sta.eb(u);
			continue;
		}
		temp = ask(sta.back(),u,rt);
		if(temp == rt){
			inq[sta.back()] = 0;
			sta.pop_back();
		}else{
			sta.eb(u);
			inq[u] = 1;
		}
	}
//	for(int u:sta) cerr << u << " ";
//	cerr << endl;
	rep(i,1,N){
		if(occ[i].empty()) continue;
		if(!sta.empty()) temp = ask(sta.back(),occ[i][0],rt);
		else temp = rt;

		if(temp == rt){
			int pos = 0;
			while(pos < SZ(occ[i])){
				if(sta.empty()) break;
				inq[sta.back()] = 0;
				sta.pop_back();
				pos++;
			}
			while(pos < SZ(occ[i])){
				sta.eb(occ[i][pos]);
				inq[occ[i][pos]] = 1;
				pos++;
			}
		}else{
			for(int u:occ[i]){
				sta.eb(u);
				inq[u] = 1;
			}
		}
	}

	if(sta.empty()){
		rep(u,1,n) if(u != rt) frp[u] = 0;
		return;
	}
	int c = sta.back();
	rep(u,1,n) if(!inq[u] && !frp[u] && u != rt && ask(u,c,rt) != rt) inq[u] = 1;
	rep(i,1,N){
		if(occ[i].empty()) continue;
		temp = ask(c,occ[i][0],rt);
		if(temp != rt) for(int u:occ[i]) inq[u] = 1;
	}
//	cerr << "remaining:\n";
//	rep(u,1,n) if(inq[u]) cerr << u << " ";
//	cerr << endl;
	int ssum = 0;
	rep(u,1,n) ssum += inq[u];
//	cerr << ssum << " " << n / 2 << endl;
	if(ssum <= n / 2){
		rep(u,1,n) if(u != rt) frp[u] = N;
//		cerr << "report" << rt << endl;
//		rep(u,1,n) cerr << frp[u] << " ";
//		cerr << endl;
		return;
	}
	rep(u,1,n) if(!inq[u]) frp[u] = N;
}

int centroid(int id,int nn,int m){
	n = nn;
	N = 0;
	rep(i,1,n) frp[i] = 0;
//	cerr << "start find! n=" << n << endl;
	while(1){
		int k = 0,x,y,z;
		rep(i,1,n){
			if(!frp[i]) p[++k] = i;
			buc[i] = 0;
		}
//		rep(i,1,n) cerr << frp[i] << " ";
//		cerr << endl;
		assert(k != 0);
		if(k == 1) return p[1];
		if(k == 2){
			solve(p[1]);
			continue;
		}else{
			rep(i,1,k){
				x = rnd() % k + 1;
				y = rnd() % k + 1;
				z = rnd() % k + 1;
				if(x == y || x == z || y == z){
					i--;
					continue;
				}
				buc[ask(p[x],p[y],p[z])]++;
			}			
		}
		rep(i,1,k) swap(p[i],p[rnd() % i + 1]);
		int u = p[1];
		rep(i,1,k) if(buc[p[i]] > buc[u]) u = p[i];
//		cerr << buc[u] << endl;
		solve(u);
	}
}
//g++ path.cpp grader.cpp -o path.exe