#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 sol=[&](auto self,vi A,vi B)->void{
auto ask=[&](int c)->int{
vi E(n,c);
for(int x:A) E[x]=-1;
return perform_experiment(E);
};
int lim=ask(n);
vi TB;
for(int x:B) if(ask(x)^lim) TB.emplace_back(x);
B.swap(TB);
if(B.size()==1lu){for(int x:A) res[x]=B.back();return;}
shuffle(A.begin(),A.end(),rng);
int mid=A.size()>>1;
self(self,vi(A.begin(),A.begin()+mid),B);
self(self,vi(A.begin()+mid,A.end()),B);
};
vi W0,W1,init;
for(int i=0;i<n;++i){
if(col[i]) W1.emplace_back(i);
else W0.emplace_back(i);
init.emplace_back(i);
}
sol(sol,W0,init);
sol(sol,W1,init);
return res;
}