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

int n;
vector<int> g[NN];
int tot;
bool vis[NN];

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

int calc(vector<int> &col,int n) {
  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,n,col);
    res++;
  }
  return res;
}

void solve(int u,vector<int> &arr,vector<int> &col,int L,int R) {
  vector<int> a,b;
  a.resize(n,n);
  b.resize(n,n);
  a[u]=col[u];
  b[u]=-1;
  if(L==R) {
    for(int i=L;i<=R;i++) a[arr[i]]=col[arr[i]],b[arr[i]]=-1;
    int val1=calc(a,n),val2=perform_experiment(b);
    if(val1!=val2) col[u]=col[arr[L]];
    return ;
  }
  int mid=L+R>>1;
  for(int i=L;i<=mid;i++) a[arr[i]]=col[arr[i]],b[arr[i]]=-1;
  int val1=calc(a,n),val2=perform_experiment(b);
  if(val1!=val2) solve(u,arr,col,L,mid);
  else solve(u,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]);
    }
    tot=0;
    for(int i=1;i<n;i++) {
      vector<int> arr;
      col[i]=++tot;
      sort(g[i].begin(),g[i].end());
      for(int j:g[i]) {
        if(j<i) arr.push_back(j);
      }
      solve(i,arr,col,0,arr.size()-1);
    }
    return col;
}