#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
#define cerr if(0) cerr
const int N = 250;
struct Dsu{
vi s, p;
Dsu(int n){
s.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return p[v] = find(p[v]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if(u != v){
if(s[u] > s[v]) swap(u, v);
s[v] += s[u];
p[u] = v;
}
}
};
mt19937 rng(31);
int rn(int l, int r){
return uniform_int_distribution<int>(l,r)(rng);
}
bitset<N> IS[N];
vi g[N];
int n;
int ask(vi E){
return perform_experiment(E);
}
void eras(vi &v, int x){
for(int j = 0; j < (int) v.size(); ++j){
if(v[j] == x){
v.erase(v.begin() + j);
return;
}
}
}
int max_case(vi &E){
int cnt = n;
Dsu d(n);
for(int i = 0; i < n; ++i){
if(E[i] == -1){
continue;
}
for(int j: g[i]){
if(E[i] == E[j] && d.find(i) != d.find(j)){
d.merge(i, j);
--cnt;
}
}
}
return cnt;
}
bitset<N> any_edge[N];
std::vector<int> find_colours(int nn, std::vector<int> X, std::vector<int> Y) {
n = nn;
int m = X.size();
for(int i = 0; i < n; ++i) g[i].clear(), IS[i] = 0;
for(int i = 0; i < m; ++i) g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]), any_edge[X[i]][Y[i]] = any_edge[Y[i]][X[i]] = 1;;
vi col(n, -1);
int sum = n;
vector<vi> COL(n);
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
COL[i].pb(j);
swap(COL[i][j], COL[i][rn(0, j)]);
}
}
int at_most = 0;
while(sum > 0 ){
at_most++;
vi v;
for(int i = 0; i < n; ++i) if(col[i] == -1) v.pb(i);
vector<int> E(n, n);
for(int i = 0; i < (int) v.size(); ++i) swap(v[i], v[rn(0, i)]);
vi search_set;
vector<pair<vi, int>> who(n, {vi{}, -1});
for(int i = 0; i < (int) v.size(); ++i){
int u = v[i];
if(E[u] == n){
int cnt = 0;
for(int j: g[u]){
if(E[j] == -1) cnt = -N*N;
else if(E[j] == n) cnt++;
else if(IS[u][E[j]] == 0){
++cnt;
}
}
if(cnt <= 0) continue;
E[u] = -1;
search_set.pb(u);
for(int j : g[u]){
if(E[j] == n){
if(COL[u].size()){
IS[u][COL[u].back()] = 1;
who[j].ss = COL[u].back();
E[j] = COL[u].back();
COL[u].pop_back();
}
}else{
IS[u][E[j]] = 1;
eras(COL[u], E[j]);
}
}
}
}
if(search_set.empty()){
continue;
}
vi check_set;
for(int i = 0; i < n; ++i) if(who[i].ss != -1){
check_set.pb(i);
for(int j: g[i]) if(E[j] == -1) who[i].ff.pb(j);
}
int qq = ask(E);
int cnt = max_case(E);
if(qq != cnt){
int L = 0;
int mx = int(check_set.size());
while(L < mx){
int l = L, r = mx - 2, res = mx - 1;
while(l <= r){
int mid = l+r>>1;
vi EE(n, n);
for(int x: search_set) if(col[x] == -1) EE[x] = -1;
for(int i = L; i <= mid; ++i) EE[check_set[i]] = who[check_set[i]].ss;
int qq = ask(EE);
int cnt = max_case(EE);
if(qq != cnt){
res = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
int node = check_set[res];
while(true){
bool ok = false;
for(int u: who[node].ff){
if(col[u] != -1){
ok = true;
eras(who[node].ff, u);
}
}
if(!ok) break;
}
int max_size = int(who[node].ff.size());
int L2 = 0;
for(int x: who[node].ff){
assert(any_edge[x][node] == 1);
for(int y : who[node].ff){
if(x != y){
assert(any_edge[x][y] == 0);
}
}
}
while(L2 < max_size){
int lp = L2, rp = max_size - 2, resp = max_size - 1;
while(lp <= rp){
vi EE(n, n);
int mid = lp+rp>>1;
for(int j = L2; j <= mid; ++j) if(col[who[node].ff[j]] == -1) EE[who[node].ff[j]] = -1;
EE[node] = who[node].ss;
int qq = ask(EE);
int cnt = max_case(EE);
if(qq != cnt){
resp = mid;
rp = mid - 1;
}else{
lp = mid + 1;
}
}
L2 = resp + 1;
int vv = who[node].ff[resp];
col[vv] = who[node].ss;
if(L2 == max_size) break;
vi EE(n, n);
for(int j = L2; j < max_size; ++j) if(col[who[node].ff[j]] == -1) EE[who[node].ff[j]] = -1;
EE[node] = who[node].ss;
int qq = ask(EE);
int cnt = max_case(EE);
if(qq == cnt) break;
}
L = res + 1;
if(L == mx) break;
vi EE(n, n);
for(int x: search_set) if(col[x] == -1) EE[x] = -1;
for(int i = L; i < mx; ++i) EE[check_set[i]] = who[check_set[i]].ss;
int qq = ask(EE);
int cnt = max_case(EE);
if(qq == cnt) break;
}
}
sum = 0;
for(int j = 0; j < n; ++j) sum += col[j] == -1;
}
return col;
}
