//仿佛只要伸手 就能触摸
#include<bits/stdc++.h>
#include "altar.h"
using namespace std;
int nxt[305][305];
int to[305];
vector<pair<int,int> >e;
int fa[305],ok[305];
int find(int x){
	if(fa[x] == x)return x;
	return fa[x] = find(fa[x]);
}
int altar(int n){
	e.clear();
	for(int i =0;i<=n;i++)to[i] = 0,fa[i] = i,ok[i] = 0;
	srand(time(0));
	for(int i =0;i<=n;i++)for(int j =0;j<=n;j++)nxt[i][j] = -1;
	vector<int>p;
	for(int i = 1;i<=n;i++)p.push_back(i);
	random_shuffle(p.begin(),p.end());
	while(p.size()>=2){
		int x = p.back();p.pop_back();int y = p.back();p.pop_back();
		int cc = sense(x,y);
		nxt[x][y] = cc,nxt[y][x] = cc^1;
		if(cc){
			to[y] = x;
			p.push_back(x);
		}else{
			to[x] = y;
			p.push_back(y);
		}
	}
	int x = p[0];p.clear();
	for(int i = 1;i<=n;i++)if(x!=i and !nxt[i][x])p.push_back(i);
	random_shuffle(p.begin(),p.end());
	for(auto y:p){
		if(sense(y,x)){
			to[x] = y;break;
		}
	}
	if(!to[x])return x;
	
	//现在我们有一个基环森林，在每个连通块上找出来一个环
	for(int i = 1;i<=n;i++)e.push_back({i,to[i]});
//	for(int i = 1;i<=n;i++)cout << " " << i << " " << to[i] << endl;
	random_shuffle(e.begin(),e.end());
	vector<int>S;
	for(int i = 0;i<e.size();i++){
		int x = e[i].first,y = e[i].second;
		if(ok[find(x)] or ok[find(y)])continue;
		if(find(x) == find(y)){
			S.push_back(x);ok[find(x)] = 1;
			continue;
		}
		ok[find(x)]|=find(y);
		fa[find(x)] = find(y);
	}
	
	int res = S[0];
	for(int i = 1;i<S.size();i++)if(sense(res,S[i]))res = S[i];
	return res;
}
/*
g++ grader.cpp qoj9909.cpp -o qwq  -O2 -std=c++14 -lm
*/