#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;
}

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 function ‘int centroid(int, int, int)’:
answer.code:256:16: error: ‘u’ was not declared in this scope
  256 |         return u;
      |                ^
answer.code: In function ‘int solveChain()’:
answer.code:198:1: warning: control reaches end of non-void function [-Wreturn-type]
  198 | }
      | ^