#include "path.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int N = 300005;

int n, cnt, tot, a[N], b[N], p[N], q[N];

int solve(int x, int y)
{
	cnt = tot = 0;
	for(int i = 1; i <= n; ++ i)
		a[i] = b[i] = 0;

	for(int i = 1; i <= n; ++ i)
	{
		if(i == x || i == y)
			continue;
		int u = ask(i, x, y);
		if(u == 0)
			a[i] = 0, p[++cnt] = i;
		else if(u == i)
			a[i] = 1, q[++tot] = i, p[++cnt] = i;
		else if(u == x)	
			a[i] = 2;
		else
			a[i] = 3;
	}

	if(!cnt) 
		return -1;

	int z = p[rand() % cnt + 1], u, v = x, w = y;
	for(int i = 1; i <= tot; ++ i)
	{
		if(q[i] == z)
			u = q[i];
		else
		{
			int t1 = ask(z, q[i], v), t2 = ask(z, q[i], w);
			if(t1 == q[i] && t2 == q[i])
				u = q[i];
			else if(t1 == q[i])
				v = q[i];
			else if(t2 == q[i])
				w = q[i];
		}
	}

	int s1 = 1;
	for(int i = 1; i <= n; ++ i)
		if(i != u && i != v)
			if(ask(i, v, u) == v)
				++ s1, b[i] = 1;

	if(s1 > n / 2)
		return solve(x, u);
	
	int s2 = 1;
	for(int i = 1; i <= n; ++ i)
		if(i != u && i != w)
			if(ask(i, w, u) == w)
				++ s2, b[i] = 1;

	if(s2 > n / 2)
		return solve(y, u);

	if(n - s1 - s2 - 1 <= n / 2)
		return u;
	
	int sum = 0, k = 0;
	b[v] = b[w] = 1;
	for(int i = 1; i <= n; ++ i)
	{
		if(b[i] || i == u)
			continue;
		if(sum == 0)
			k = i, ++ sum;
		else
		{
			if(ask(i, u, k) != u)
				++ sum;
			else
				-- sum;
		}
	}

	sum = 1;
	for(int i = 1; i <= n; ++ i)
		if(!b[i] && i != u && i != k && ask(i, u, k) != u)
			++ sum;
	
	if(sum > n / 2)
		return -1;

	return u;
}

int centroid(int id, int N, int M)
{
	if(id == 1)
		return ask(1, 2, 3);

	n = N;
	int x = rand() % n + 1, y = rand() % n + 1;
	while(x == y)
		y = rand() % n + 1;
	int u = solve(x, y);
	while(u == -1)
	{
		x = rand() % n + 1;
		y = rand() % n + 1;
		while(x == y)
			y = rand() % n + 1;
		u = solve(x, y);
	}

	// printf("%d\n", u);
	return u;
}