#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)
{
    // printf("%d %d\n", x, y);
	cnt = tot = 0;
	for(int i = 1; i <= n; ++ i)
		b[i] = 0;

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

	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, s2 = 1;
	for(int i = 1; i <= n; ++ i)
    {
		if(i == u)
			continue;
        if(a[i] == 2)
        {
            ++ s1;
            b[i] = 2;
            continue;
        }
        if(a[i] == 3)
        {
            ++ s2;
            b[i] = 3;
            continue;
        }
        if(i == v)
        {
            b[i] = 4;
            continue;
        }
        if(i == w)
        {
            b[i] = 5;
            continue;
        }
        int t1 = ask(i, v, u), t2 = ask(i, w, u);
        if(t1 == v && a[i] == 1)
        {
            ++ s1;
            b[i] = 4;
            continue;
        }
        if(t2 == w && a[i] == 1)
        {
            ++ s2;
            b[i] = 5;
            continue;
        }
        if(t1 == v && a[i] == 0)
        {
            ++ s1;
            b[i] = 6;
            continue;
        }
        if(t2 == w && a[i] == 0)
        {
            ++ s2;
            b[i] = 7;
            continue;
        }
        b[i] = 1;
    }

	if(s1 > n / 2)
	{
        for(int i = 1; i <= n; ++ i)
        {
            if(b[i] == 2)
                a[i] = 2;
            else if(b[i] == 4)
                a[i] = 1;
            else if(b[i] == 6)
                a[i] = 0;
            else
                a[i] = 3;
        }
        a[x] = a[u] = 0;
		return solve(x, u);
	}

	if(s2 > n / 2)
	{
        for(int i = 1; i <= n; ++ i)
        {
            if(b[i] == 3)
                a[i] = 3;
            else if(b[i] == 5)
                a[i] = 1;
            else if(b[i] == 7)
                a[i] = 0;
            else
                a[i] = 2;
        }
        a[u] = a[y] = 0;
		return solve(u, y);
	}

	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] != 1 || 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] == 1 && i != u && i != k && ask(i, u, k) != u)
			++ sum;
	
	if(sum > n / 2)
		return -1;

	return u;
}

int solveChain()
{
	for(int i = 1; i <= n; ++ i)	
		a[i] = 0;
	p[1] = 1;
	p[2] = 2;
	for(int i = 3; i <= n; ++ i)
	{
		p[3] = i;
		int u = ask(p[1], p[2], p[3]);
		if(u == p[1])
			p[1] = p[3];
		else if(u == p[2])
			p[2] = p[3];
	}

	int u = p[1];
	// printf("%d\n", u);
	for(int i = 1; i <= n; ++ i)
	{
		for(int j = i + 1; j <= n; ++ j)
		{
			if(i != j && i != u && j != u)
			{
				if(ask(u, i, j) == i)
					++ a[j];
				else
					++ a[i];
			}
		}
		if(a[i] + 1 == n / 2)
			return i;
	}
}

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

	// int x = rand() % n + 1, y = rand() % n + 1;
	// while(x == y)
	// 	y = rand() % n + 1;
    
	// for(int i = 1; i <= n; ++ i)
	// {
	// 	a[i] = 0;
	// 	if(i == x || i == y)
	// 		continue;
	// 	int u = ask(i, x, y);
	// 	if(u == 0)
	// 		a[i] = 0;
	// 	else if(u == i)
	// 		a[i] = 1;
	// 	else if(u == x)	
	// 		a[i] = 2;
	// 	else
	// 		a[i] = 3;
	// }

	// int u = solve(x, y);
	// while(u == -1)
	// {
	// 	x = rand() % n + 1;
	// 	y = rand() % n + 1;
	// 	while(x == y)
	// 		y = rand() % n + 1;
            
    //     for(int i = 1; i <= n; ++ i)
    //     {
	// 		a[i] = 0;
    //         if(i == x || i == y)
    //             continue;
    //         int u = ask(i, x, y);
    //         if(u == 0)
    //             a[i] = 0;
    //         else if(u == i)
    //             a[i] = 1;
    //         else if(u == x)	
    //             a[i] = 2;
    //         else
    //             a[i] = 3;
    //     }
	// 	u = solve(x, y);
	// }

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