#include<bits/stdc++.h>
#include "path.h"
using namespace std;

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;
	vector<int> cur;
	for(auto v : tr)
		if(cur.empty()) cur.push_back(v);
		else {
			if(ask(cur.back(), x, v)) 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))
				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);
	
	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;
	for(int i = 1; i <= n; ++ i)
		f[i] = i, vis[i] = -1;
	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:6:7: error: ‘N’ was not declared in this scope
    6 | int f[N], vis[N];
      |       ^
answer.code:6:15: error: ‘N’ was not declared in this scope
    6 | int f[N], vis[N];
      |               ^
answer.code: In function ‘int find(int)’:
answer.code:9:26: error: ‘f’ was not declared in this scope
    9 | int find(int u) { return f[u] == u ? u : f[u] = find(f[u]); }
      |                          ^
answer.code: In function ‘void merge(int, int)’:
answer.code:10:54: error: ‘f’ was not declared in this scope
   10 | void merge(int u, int v) { u = find(u), v = find(v), f[u] = v; }
      |                                                      ^
answer.code: In function ‘int check(int, std::vector<int>)’:
answer.code:22:9: error: ‘vis’ was not declared in this scope
   22 |         vis[find(cur.back())] = 1;
      |         ^~~
answer.code: In function ‘int centroid(int, int, int)’:
answer.code:116:17: error: ‘f’ was not declared in this scope
  116 |                 f[i] = i, vis[i] = -1;
      |                 ^
answer.code:116:27: error: ‘vis’ was not declared in this scope
  116 |                 f[i] = i, vis[i] = -1;
      |                           ^~~