#include<bits/stdc++.h>
#include "path.h"
using namespace std;
const int N = 5e4 + 5;

mt19937 rnd(time(0));
int f[N], vis[N];
int n;

int find(int u) { return f[u] == u ? u : f[u] = find(f[u]); }
void merge(int u, int v) { u = find(u), v = find(v), f[u] = v; }

int check(int x, vector<int> tr) {
	if(tr.size() <= n / 2) return x;
	for(int i = 1; i <= n; ++ i)
		f[i] = i, vis[i] = -1;
	vector<int> cur;
	for(auto v : tr)
		if(cur.empty()) cur.push_back(v);
		else {
			if(ask(cur.back(), x, v) == x) cur.pop_back();
			else merge(cur.back(), v), cur.push_back(v);
		}
	if(cur.empty()) return x;
	vis[find(cur.back())] = 1;
	int cnt = 0;
	for(auto v : tr) {
		if(vis[find(v)] != -1) cnt += vis[find(v)];
		else {
			if(ask(cur.back(), x, v) == x)
				vis[find(v)] = 0;
			else ++ cnt, vis[find(v)] = 1;
		} 
		if(cnt > n / 2) return -1;
	}
	return x;
}

int find(int x, int y, vector<int> tx, vector<int> ty, vector<int> in, vector<int> out) {
	if(tx.size() > n / 2) return check(x, tx);
	if(ty.size() > n / 2) return check(y, ty);
	if(x == y) return check(x, out);
	
	int u = -1, cnt = rnd() % (in.size() + out.size());
	if(cnt < in.size()) u = in[cnt];
	else {
		int v = out[cnt - in.size()];
		u = x;
		for(auto i : in)
			if(ask(u, i, v) == i) u = i; 
	}
	
	vector<int> ul, ur, ulo, uro, tu;
	for(auto v : in) {
		if(v == u) continue;
		if(ask(x, u, v) == v) ul.push_back(v);
		else ur.push_back(v);
	}
	for(auto v : out)
		if(ask(x, u, v) == u) {
			if(ask(y, u, v) == u) tu.push_back(v);
			else uro.push_back(v);
		} else ulo.push_back(v);
	
	int sizl = ulo.size() + ul.size() + tx.size();
	int sizr = uro.size() + ur.size() + ty.size();
	if(sizl <= n / 2 && sizr <= n / 2) return check(u, tu);
	
	if(sizl > n / 2){
		int mx = x;
		for(int v : ul) {
			if(v == x)continue;
			if(ask(x, v, mx) == mx) mx = v;
		}
		vector<int> nwout;
		for(int v : ulo){
			if(ask(v, mx, x) == mx) ty.push_back(v);
			else nwout.push_back(v);
		}
		ty.push_back(u);
		for(int v : ur) ty.push_back(v);
		for(int v : uro) ty.push_back(v);
		for(int v : tu) ty.push_back(v);
		return find(x, mx, tx, ty, ul, nwout);
	}
	else {
		int mn = y;
		for(int v : ur){
			if(v == y)continue;
			if(ask(y, v, mn) == mn) mn = v;
		}
		vector<int> nwout;
		for(int v : uro){
			if(ask(v, mn, y) == mn) tx.push_back(v);
			else nwout.push_back(v);
		}
		tx.push_back(u);
		for(int v : ul) tx.push_back(v);
		for(int v : ulo) tx.push_back(v);
		for(int v : tu) tx.push_back(v);
		return find(mn, y, tx, ty, ur, nwout);
	}
} 
int solve(int x, int y) {
	vector<int> tx, ty, in, out;
	for(int i = 1; i <= n; ++ i) 
		if(i == x || i == y) in.push_back(i);
		else {
			int r = ask(x, y, i);
			if(r == x) tx.push_back(i);
			if(r == y) ty.push_back(i);
			if(r == i) in.push_back(i);
			if(r == 0) out.push_back(i); 
		}
	return find(x, y, tx, ty, in, out);
}
int centroid(int id, int N, int M) {
	n = N;
	if(id == 1) return ask(1, 2, 3);
	if(id == 5) {
		int l = 1, r = 2;
		for(int i = 3; i <= n; ++ i) {
			int res = ask(l, r, i);
			if(res == l) l = i;
			if(res == r) r = i;
		}	
		vector<int> all;
		for(int i = 1; i <= n; ++ i) all.push_back(i);
		nth_element(all.begin(),all.begin()+n/2,all.end(),[](int x,int y){
			return ask(l,x,y)==x;
		});
		return all[n/2];
	}
	while(1) {
		int x = rnd() % n + 1, y = rnd() % n + 1;
		int res = solve(x, y);
		if(res != -1) return res;  
	}
	return 114514;
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:60:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         fread(Interactor::rbuf,1,50000000,stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In lambda function:
answer.code:130:36: error: ‘l’ is not captured
  130 |                         return ask(l,x,y)==x;
      |                                    ^
answer.code:129:68: note: the lambda has no capture-default
  129 |                 nth_element(all.begin(),all.begin()+n/2,all.end(),[](int x,int y){
      |                                                                    ^
answer.code:121:21: note: ‘int l’ declared here
  121 |                 int l = 1, r = 2;
      |                     ^