#include "altar.h"
#include<bits/stdc++.h>
using namespace std;
const int N=309;
int v[N],vis[N];
int d[N][N];
mt19937 rd(time(0));
bool get(int x,int y)
{
	if(d[x][y]!=-1)
	return d[x][y];
	d[x][y]=sense(x,y);
	d[y][x]=d[x][y]^1;
	return d[x][y];
}
int altar(int n)
{
	memset(d,-1,sizeof(d));
	memset(v,0,sizeof(v));
	memset(vis,0,sizeof(vis));
	int num=n,now=n;
	while(num>1)
	{
		int x=rd()%now+1;
		int p=0;
		for(int i=1;i<=n;i++)
		{
			if(v[i]||vis[i])
			continue;
			x--;
			if(!x)
			{
				p=i;
				break;
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(!v[i])
			{
				v[i]=get(p,i);
				num-=v[i];
				if(!vis[i]&&v[i])
				now--;
			}
		}
		vis[p]=1;
		now--;
	}
	for(int i=1;i<=n;i++)
	if(!v[i])
	return i;
	return 0;
}