#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(chrono::steady_clock::now().time_since_epoch().count());
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;
}
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]);
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<pii> who(n, {-1, -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] == n) cnt++;
else{
cnt = -N*N;
}
}
if(cnt <= 0) continue;
E[u] = -1;
search_set.pb(u);
for(int j : g[u]){
if(E[j] == n){
if(COL[u].size()){
who[j] = {u, COL[u].back()};
E[j] = COL[u].back();
COL[u].pop_back();
}else{
E[j] = 0; // nothing to do with this guy, it should be marked tho
who[j] = {u, 0};
}
}
}
}
}
if(search_set.empty()){
continue;
}
vi check_set;
for(int i = 0; i < n; ++i) if(who[i].ff != -1) check_set.pb(i);
cerr << '\n';
cerr << '\n';
int qq = ask(E);
// what should this guy be if all of them are not good
int cnt = max_case(E);
if(qq != cnt){
cerr << "there is something \n";
// there is something...
// we gotta bs
bitset<N> in_set = 0;
for(int x: search_set) in_set[x] = 1;
int L = 0;
int mx = int(check_set.size());
while(L < mx){
int l = L, r = mx - 1, res = mx;
while(l <= r){
int mid = l+r>>1;
vi EE(n, n);
for(int x: search_set) EE[x] = -1;
for(int i = L; i <= mid; ++i) EE[check_set[i]] = who[check_set[i]].ss;
cerr << "bs query\n";
for(int x: EE){
cerr << x << ' ';
}
int qq = ask(EE);
int cnt = max_case(EE);
cerr << qq << ' ' << cnt << ' ' << mid << " f\n";
cerr << "\n";
cerr << "\n";
if(qq != cnt){
res = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
if(res == mx) break;
int node = check_set[res];
col[who[node].ff] = who[node].ss;
L = res + 1;
vi EE(n, n);
for(int x: search_set) 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;
}
