#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
const int NN=260;

int n;
vector<int> g[NN],gc[NN];
int tot;
bool vis[NN];
int cc[NN],ctot,rc[NN];
vector<int> c[NN];

void dfs(int u,vector<int> &col) {
  vis[u]=1;
  for(int v:g[u]) {
    if(vis[v]) continue;
    if(col[u]!=col[v]) continue;
    dfs(v,col);
  }
}

int calc(vector<int> &col) {
  for(int i=0;i<n;i++) vis[i]=0;
  int res=0;
  for(int i=0;i<n;i++) {
    if(vis[i]) continue;
    dfs(i,col);
    res++;
  }
  return res;
}

int solve(vector<int> &arr,int col,int L,int R) {
  if(L==R) return L;
  vector<int> a,b;
  a.resize(n,col);
  b.resize(n,col);
  int mid=L+R>>1;
  for(int i=L;i<=mid;i++) a[arr[i]]=n,b[arr[i]]=-1;
  int val1=calc(a),val2=perform_experiment(b);
  if(val1!=val2) return solve(arr,col,L,mid);
  else return solve(arr,col,mid+1,R);
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y) {
    n=N;
    vector<int> col;
    col.resize(n);
    int m=X.size();
    for(int i=0;i<m;i++) {
      if(X[i]>Y[i]) swap(X[i],Y[i]);
      g[X[i]].push_back(Y[i]),g[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<2;i++) {
      vector<int> arr;
      for(int j=i;j<n;j+=2) arr.push_back(j);
      for(int j=0;j<n;j++) {
        while(arr.size()) {
          vector<int> a,b;
          a.resize(n,j),b.resize(n,j);
          for(int k:arr) a[k]=n,b[k]=-1;
          if(calc(a)==perform_experiment(b)) break;
          int ps=solve(arr,j,0,arr.size());
          col[arr[ps]]=j;
          vector<int> arrr;
          for(int k:arr) if(k!=arr[ps]) arrr.push_back(k);
          swap(arr,arrr);
        }
      }
    }
    return col;
    // tot=0;
    // for(int i=1;i<n;i++) {
    //   col[i]=++tot;
    //   sort(g[i].begin(),g[i].end());
    //   do{
    //     vector<int> arr;
    //     for(int j:g[i]) {
    //       if(j<i && col[j]!=col[i]) arr.push_back(j);
    //     }
    //     vector<int> a,b;
    //     a.resize(n,n),b.resize(n,n);
    //     for(int j:arr) a[j]=col[j],b[j]=-1;
    //     a[i]=col[i],b[i]=-1;
    //     if(calc(a)==perform_experiment(b)) break;
    //     int val=solve(i,arr,col,0,arr.size()-1);
    //     if(val==-1) break;
    //     for(int j=0;j<n;j++) if(col[j]==val) col[j]=col[i]; 
    //   }while(1);
    // }
    // for(int i=0;i<n;i++) vis[i]=0;
    // ctot=0;
    // for(int i=0;i<n;i++) {
    //   if(vis[i]) continue;
    //   ctot++;
    //   dfss(i,col,ctot);
    // }
    // if(ctot==1) {
    //   for(int i=0;i<n;i++) {
    //     vector<int> b;
    //     b.resize(n,-1);
    //     b[0]=i;
    //     if(perform_experiment(b)==1) {
    //       vector<int> res;
    //       res.resize(n,i);
    //       return res;
    //     }
    //   }
    // }
    // for(int i=0;i<n;i++) col[i]=rc[cc[i]];
    // return col;
}