#include "sphinx.h"
#include <random>
#include <vector>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
vi find_colours(int n,vi X,vi Y){
	mt19937 rng(20070329);
	vector<vi> adj(n);
	int m=max(X.size(),Y.size());
	for(int i=0;i<m;++i){
		adj[X[i]].emplace_back(Y[i]);
		adj[Y[i]].emplace_back(X[i]);
	}
	vi vis(n),col(n);
	auto dfs=[&](auto self,int u)->void{
		vis[u]=1;
		for(int v:adj[u]){
			if(vis[v]) continue;
			col[v]=col[u]^1;
			self(self,v);
		}
	};
	dfs(dfs,rng()%n);
	vi res(n,-1);
	auto ask=[&](vi VC,int c)->int{
		vi E(n,c);
		for(int x:VC) E[x]=-1;
		if(c==n){
			int ans=n;
			for(int i=1;i<n;++i)
				if(E[i]==n&&E[i-1]==n) --ans;
			return ans;
		}
		else return perform_experiment(E);
	};
	int cnt=0;
	auto sol=[&](auto self,vi A,vi B,int L)->void{
		if(B.size()==1lu){for(int x:A) res[x]=B.back();return;}
		// shuffle(A.begin(),A.end(),rng);
		int mid=A.size()>>1;
		vi A0(A.begin(),A.begin()+mid),A1(A.begin()+mid,A.end());
		int sz=B.size(),L0=ask(A0,n),L1=ask(A1,n);
		vi B0,B1;
		for(int i=0;i<sz;++i){
			int tmp=ask(A0,B[i]);
			if(tmp^L0) B0.emplace_back(B[i]);
			else B1.emplace_back(B[i]);
		}
		self(self,A0,B0,L0);
		if(B0.size()+A1.size()>B.size()){
			for(int x:B0) if(ask(A1,x)^L1) B1.emplace_back(x);
		}
		self(self,A1,B1,L1);
	};
	vi A0,A1,B0,B1;
	for(int i=0;i<n;++i){
		if(col[i]) A1.emplace_back(i);
		else A0.emplace_back(i);
	}
	int L0=ask(A0,n),L1=ask(A1,n);
	for(int i=0;i<n;++i){
		int tmp;
		tmp=ask(A0,i);
		if(tmp^L0) B0.emplace_back(i);
		tmp=ask(A1,i);
		if(tmp^L1) B1.emplace_back(i);
	}
	sol(sol,A0,B0,L0);
	sol(sol,A1,B1,L1);
	return res;
}