#include "sphinx.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
  if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
  if(x > y) x = y;
}

inline int popcnt(int x){
  return __builtin_popcount(x);
}

inline int ctz(int x){
  return __builtin_ctz(x);
}
int n;
vector <int> G[255];
int fa[255],col[255],vis[255],cur[255],ord[255];
int fnd(int u){
    if(fa[u] == u) return u;
    return fa[u] = fnd(fa[u]);
}
void mrg(int u,int v){
    u = fnd(u);v = fnd(v);
    if(u == v) return;
    fa[u] = v;
}

int test(vector <int> &C){
    rep(u,1,n) fa[u] = u;
    rep(u,1,n){
        for(int v:G[u]){
            if(C[u - 1] == C[v - 1]) mrg(u,v);
        }
    }
    int result = 0;
    rep(u,1,n) result += fa[u] == u;
    return result;
}

int query(vector <int> &C){
    assert(SZ(C) == n);
    int ret = perform_experiment(C);
//    for(int c:C) printf("%d ",c);
//    printf("ret=%d\n",ret);
    return ret;
}

bool cmp(int x,int y){
    return cur[x] < cur[y];
}

int check(vector <int> &C){
    int res1 = test(C),res2 = query(C);
//    for(int c:C) printf("%d ",c);
//    printf("\n%d %d\n",res1,res2);
    return res1 == res2;
}
int sz;
pii idx[255];
vector <int> find_colours(int N, vector<int> X,vector<int> Y) {
    n = N;
    rep(i,0,SZ(X) - 1){
        X[i]++;Y[i]++;
        G[X[i]].eb(Y[i]);
        G[Y[i]].eb(X[i]);
    }
    rep(u,1,n) cur[u] = 0;
    vector <int> ans(n),C(n),CC(n);
    while(1){
        rep(u,1,n){
            ord[u] = u;
            vis[u] = 0;
        }
        sort(ord + 1,ord + n + 1,cmp);
        if(cur[ord[1]] >= n) break;

        sz = 0;
        rep(_i,1,n){
            int u = ord[_i];
            if(vis[u]) continue;
            vis[u] = 1;
            col[u] = -1;
            for(int v:G[u]){
                if(vis[v]) continue;
                vis[v] = 1;
                col[v] = cur[u]++;
                idx[++sz] = mkp(u,v);
//                printf("%d:(%d,%d)\n",sz,u,v);
                chkmin(cur[u],n);
            }
        }
//        rep(u,1,n) printf("%d ",col[u]);
//        printf("\n");
        rep(u,1,n){
            if(!vis[u]) col[u] = n;
            C[u - 1] = col[u];
        }
        if(check(C)) continue;

        int pl = 1,pr = sz,mid;
        while(pl != pr){
            mid = (pl + pr) >> 1;
            CC = C;
            rep(i,1,pl - 1) CC[idx[i].second - 1] = n;
            rep(i,mid+1,sz) CC[idx[i].second - 1] = n;
            if(check(CC)) pl = mid + 1;
            else pr = mid;
        }
        ans[idx[pl].first - 1] = col[idx[pl].second];
    }
    return ans;
}
/*
g++ sphinx3.cpp grader.cpp -o grader3.exe -Wall -Wshadow -O2 -std=c++14
*/