#include "sphinx.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int msz = 256;
int perform_experiment(vector<int> E);
//47.5 points
int n , m;
vector<int> G , g[msz] , col;
vector<bool> w;
void dfs(int v){
w[v] = 1;
for(auto to : g[v]){
if((! w[to]) and col[to] == col[v]){
dfs(to);
}
}
}
int expected(){
w = vector<bool> (n , 0);
int cmp = 0;
for(int i = 0;i < n; ++ i){
if(! w[i]){
cmp ++;
dfs(i);
}
}
return cmp;
}
vector<int> find_colours(int N, std::vector<int> x, std::vector<int> y) {
n = N , m = x.size();
G = vector<int> (n , 0);
bool ok = true;
for(int i = 0;i < m; ++ i){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
if(x[i] != i or y[i] != i + 1) ok = false;
}
if(n <= 52){
col = vector<int> (n , n);
for(int i = 0;i < n; ++ i){
col[i] = -1;
col[g[i][0]] = -1;
int cmp = expected();
for(int j = 0;j < n; ++ j){
vector<int> qu(n , n);
qu[i] = -1;
qu[g[i][0]] = j;
if(perform_experiment(qu) == cmp){
G[i] = j;
break;
}
}
col[i] = n;
col[g[i][0]] = n;
}
return G;
}
if(m == (n * (n - 1)) / 2){
for(int i = 0;i < n; ++ i){
int l = 0;
int r = n;
while(l + 1 < r){
int mid = (l + r) / 2;
vector<int> qu(n , n);
qu[i] = -1;
for(int j = 0;j < (r - mid); ++ j){
qu[g[i][j]] = mid + j;
}
if(perform_experiment(qu) == (r - mid + 1)) l = mid;
else r = mid;
}
G[i] = l;
}
return G;
}
if(ok){
int c = 0;
for(int i = 0;i < n; ++ i){
G[i] = c;
for(int j = i + 1;j < n; ++ j){
vector<int> qu(n , n);
for(int z = i;z <= j; ++ z) qu[z] = -1;
if(perform_experiment(qu) == 1 + (i != 0) + (j != (n - 1))){
i = j;
G[j] = c;
}
else break;
}
c ++;
}
return G;
}
return G;
}
