#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef int ll;
namespace{
const ll mxN=255;
ll n, m;
vll adj[mxN];
bool visited[mxN];
void dfs(ll cur, ll u, ll v){
if(cur==u || cur==v || visited[cur]) return;
visited[cur]=1;
for(auto &it:adj[cur]){
dfs(it, u, v);
}
}
ll f(ll u, ll v){
memset(visited, 0, sizeof(visited));
ll cnt=0;
for(ll i=0;i<n;i++){
if(i==u || i==v) continue;
if(!visited[i]){
dfs(i, u, v);
cnt++;
}
}
return cnt;
}
ll ceil_div(ll a, ll b){
return (a+b-1)/b;
}
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
n=N;
m=X.size();
for(ll i=0;i<m;i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vll ans(n, -1);
auto qry=[&](ll c, ll tar){
if(tar%2==0){
vll tep(n, n);
for(ll i=1;i<n;i+=2){
tep[i]=c;
}
for(ll i=0;i<n;i+=2){
if(i>tar) break;
if(ans[i]!=-1) continue;
tep[i]=-1;
}
if(perform_experiment(tep)<n){
return true;
}
return false;
}
else{
vll tep(n, n);
for(ll i=0;i<n;i+=2){
tep[i]=c;
}
for(ll i=1;i<n;i+=2){
if(i>tar) break;
if(ans[i]!=-1) continue;
tep[i]=-1;
}
if(perform_experiment(tep)<n){
return true;
}
return false;
}
};
for(ll c=0;c<n;c++){
for(ll i=0;i<2;i++){
if(i==0){
while(true){
ll lef=0, rig=ceil_div(n, 2)-1;
if(!qry(c, rig*2)){
break;
}
ll good=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(qry(c, 2*mid)){
good=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
ans[good*2]=c;
}
}
else{
while(true){
ll lef=0, rig=n/2-1;
if(!qry(c, rig*2+1)){
break;
}
ll good=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(qry(c, 2*mid+1)){
good=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
ans[good*2+1]=c;
}
}
}
}
// cout<<qry(1, 0)<<'\n';
return ans;
}
