#include "puzzle.h"
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<random>
#define N 1000
using namespace std;
struct reads
{
	int x,y;
};
vector<reads>p[N+1];
int tn,n,length,tong[N+1],rd[N+1];
bool used[N+1];
unsigned long long seed=998244353;
vector<int>E[N+1];
unsigned long long get_rand()
{
	seed^=(seed<<7);
	seed^=(seed>>11);
	seed^=(seed<<17);
	return seed;
}
int get(int x)
{
	if (x>tn) x-=tn;
	if (x<1) x+=tn;
	return x;
}
void add_edge(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void solve(vector<reads>sp,int res)
{
	if (!res) return;
	if (sp.size()==1)
	{
		for (int i=0;i<sp.size();++i) add_edge(sp[i].x,sp[i].y);
		return;
	}
	vector<reads>A;
	vector<reads>B;
	int mid=sp.size()>>1,d;
	vector<int>tp(n);
	for (int i=1;i<=n;++i) tp[i-1]=rd[i];
	for (int i=0;i<mid;++i) A.push_back(sp[i]),tp[sp[i].x-1]=rd[sp[i].y],tp[sp[i].y-1]=rd[sp[i].x];
	for (int i=mid;i<sp.size();++i) B.push_back(sp[i]);
	d=query(tp),solve(A,d),solve(B,res-d);
	return;
}
void dfs(int x)
{
	used[x]=1,tong[++length]=x;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			dfs(E[x][i]);
	return;
}
void play(int sn)
{
	n=sn;
	vector<reads>tp;
	vector<int>sp(n);
	vector<int>ans(n);
	for (int i=0;i<n;++i) sp[i]=i;
	while (1)
	{
		for (int i=1;i<=20*n;++i) swap(sp[get_rand()%n],sp[get_rand()%n]);
		if (!query(sp)) break;
	}
	for (int i=1;i<=n;++i) rd[i]=sp[i-1];
	if (!(n&1))
	{
		tn=n-1;
		for (int i=1;i<=n-1;++i)
		{
			p[i].push_back((reads){i,n});
			for (int j=1;j<=(n>>1)-1;++j) p[i].push_back((reads){get(i-j),get(i+j)});
		}
	}
	else
	{
		tn=n;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=(n>>1);++j)
				p[i].push_back((reads){get(i-j),get(i+j)});
	}
	for (int i=1;i<=n;++i)
		if (!p[i].empty())
		{
			tp.clear();
			for (int j=0;j<p[i].size();++j)
				if (E[p[i][j].x].size()<=1&&E[p[i][j].y].size()<=1)
					tp.push_back(p[i][j]);
			if (!tp.empty())
			{
				for (int j=1;j<=n;++j) sp[j-1]=rd[j];
				for (int j=0;j<tp.size();++j) sp[tp[j].x-1]=rd[tp[j].y],sp[tp[j].y-1]=rd[tp[j].x];
				solve(tp,query(sp));
			}
		}
	for (int i=1;i<=n;++i)
		if (!used[i])
		{
			length=0,dfs(i);
			for (int j=1;j<=n;++j) sp[j-1]=rd[j];
			for (int j=1;j<=length;++j) sp[tong[j]-1]=rd[tong[j%length+1]];
			if (query(sp))
			{
				for (int j=1;j<=length;++j) ans[tong[j]-1]=rd[tong[j%length+1]];
			}
			else
			{
				for (int j=1;j<=length;++j) ans[tong[j%length+1]-1]=rd[tong[j]];
			}
		}
	check(ans);
	return;
}