#include "sphinx.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
vector<ll> g[300],g2[300];
bool col[300],odw[300];
ll par[300];
map<vector<ll>,ll>mp;
void dfs(ll v,bool cl){
if(odw[v])return;
odw[v]=1;
col[v]=cl;
for(ll i : g2[v])dfs(i,!cl);
}
ll comps(vector<ll>v){
sort(v.begin(),v.end());
if(mp[v])return mp[v]-1;
queue<ll>q;
bool odw[300];
for(ll i : v)odw[i]=0;
ll res=0;
for(ll i : v){
if(odw[i]==0){
res++;
q.push(i);
while(!q.empty()){
auto pom=q.front();
q.pop();
if(!odw[pom] && lower_bound(v.begin(),v.end(),pom)!=v.end() && *lower_bound(v.begin(),v.end(),pom)==pom){
odw[pom]=1;
for(ll j : g[pom])q.push(j);
}
}
}
}
mp[v]=res+1;
return res;
}
ll comps2(vector<vector<ll>>v){
vector<ll>v2;
for(auto i : v)for(auto j : i )v2.pb(j);return comps(v2);
}
ll zap(vector<ll>v,ll n,ll cl){
vector<int>pm;
pm.resize(n);
for(ll i=0;i<n;i++){pm[i]=n;if(col[par[i]])pm[i]=cl;}
for(ll i : v)pm[i]=-1;
vector<ll>v2;
for(ll i=0;i<n;i++)if(pm[i]==n)v2.pb(i);
return perform_experiment(pm)-comps(v2);
}
ll zap2(vector<vector<ll>>v,ll n,ll cl){
vector<ll>v2;
for(vector<ll> i : v)for(ll j : i)v2.pb(j);
return zap(v2,n,cl);
}
bool kn[300][300];
bool kn2[300][300];
vector<int>find_colours(int n,vector<int>x,vector<int>y){
for(ll i=0;i<n+7;i++){g[i].clear();g2[i].clear();odw[i]=0;}
for(ll i=0;i<x.size();i++){
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
kn[x[i]][y[i]]=1;
kn[y[i]][x[i]]=1;
}
vector<vector<ll>>cmp={{0}};
vector<ll>v;
for(ll i=1;i<n;i++){
cmp.pb({i});
ll pm=zap2(cmp,n,-1);
cmp.pop_back();
vector<ll>ak={i};
pm=cmp.size()+1-pm;
for(ll k=0;k<pm;k++){
ll pocz=0;
ll kon=cmp.size()-1;
while(pocz!=kon){
ll mid=(pocz+kon)/2;
vector<vector<ll>>query={ak};
for(ll j=pocz;j<=mid;j++)query.pb(cmp[j]);
if(zap2(query,n,-1)!=query.size()) kon=mid;
else pocz=mid+1;
}
swap(cmp[pocz],cmp.back());
for(ll j : cmp.back())ak.pb(j);
cmp.pop_back();
}
cmp.pb(ak);
}
vector<int>ans;
ans.resize(n);
if(cmp.size()==1){
vector<int>ak;
ak.resize(n);
for(ll i=0;i<n;i++)ak[i]=-1;
for(ll i=0;i<n;i++){
ak[0]=i;
if(perform_experiment(ak)==1){
for(ll j=0;j<n;j++)ans[j]=i;return ans;
}
}
}
for(ll i=0;i<cmp.size();i++){
for(ll j : cmp[i])par[j]=i;
for(ll j=0;j<cmp.size();j++){
for(ll a : cmp[i]) for(ll b : cmp[j]) if(kn[a][b])kn2[i][j]=1;
if(kn2[i][j])g2[i].pb(j);
}
}
dfs(0,0);
v.clear();
for(ll i=0;i<cmp.size();i++)if(!col[i])v.pb(i);
for(ll akcol=0;akcol<n;akcol++){
vector<vector<ll>>v2,ak;
for(ll i=0;i<cmp.size();i++)if(col[i])ak.pb(cmp[i]);
auto akold=ak;
for(ll j : v)v2.pb(cmp[j]);
ll pom=zap2(v2,n,akcol);
while(comps2(ak)+cmp.size()-ak.size()!=pom){
ll pocz=0;
ll kon=v2.size()-1;
while(pocz!=kon){
ll mid=(pocz+kon)/2;
vector<vector<ll>>query;
for(ll i=pocz;i<=mid;i++)query.pb(v2[i]);
if(zap2(query,n,akcol)!=comps2(akold)+query.size())kon=mid;
else pocz=mid+1;
}
ak.pb(v2[pocz]);
swap(v2[pocz],v2.back());
for(ll i : v2.back())ans[i]=akcol;
v2.pop_back();
}
}
for(ll i=0;i<cmp.size();i++)col[i]^=1;
v.clear();
for(ll i=0;i<cmp.size();i++)if(!col[i])v.pb(i);
for(ll akcol=0;akcol<n;akcol++){
vector<vector<ll>>v2,ak;
for(ll i=0;i<cmp.size();i++)if(col[i])ak.pb(cmp[i]);
auto akold=ak;
for(ll j : v)v2.pb(cmp[j]);
ll pom=zap2(v2,n,akcol);
while(comps2(ak)+cmp.size()-ak.size()!=pom){
ll pocz=0;
ll kon=v2.size()-1;
while(pocz!=kon){
ll mid=(pocz+kon)/2;
vector<vector<ll>>query;
for(ll i=pocz;i<=mid;i++)query.pb(v2[i]);
if(zap2(query,n,akcol)!=comps2(akold)+query.size())kon=mid;
else pocz=mid+1;
}
ak.pb(v2[pocz]);
swap(v2[pocz],v2.back());
for(ll i : v2.back())ans[i]=akcol;
v2.pop_back();
}
}
return ans;
}
