#include "sphinx.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int msz = 256;
int perform_experiment(vector<int> E);
//64 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);
for(int i = 0;i < m; ++ i){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
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);
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(m == n - 1){
for(int i = 0;i < n; ++ i){
vector<int> qu(n , n);
for(int j = 0;j < n; j += 2) qu[j] = -1;
int cnt = perform_experiment(qu) , p = -1 , k = 0;
for(int j = 0;j < cnt; ++ j){
int l = p;
int r = n / 2;
while(l + 1 < r){
int mid = (l + r) / 2;
qu = vector<int> (n , n);
for(int z = 0;z < mid; ++ z) qu[z * 2] = -1;
if(perform_experiment(qu) - k > 0) r = mid;
else l = mid;
}
qu = vector<int> (n , n);
p = r;
for(int z = 0;z <= p; ++ z) qu[p * 2] = -1;
k = perform_experiment(qu);
G[p * 2] = i;
}
qu = vector<int> (n , n);
for(int j = 1;j < n; j += 2) qu[j] = -1;
cnt = perform_experiment(qu) , p = -1 , k = 0;
for(int j = 0;j < cnt; ++ j){
int l = p;
int r = (n - 1) / 2;
while(l + 1 < r){
int mid = (l + r) / 2;
qu = vector<int> (n , n);
for(int z = 0;z < mid; ++ z) qu[z * 2 + 1] = -1;
if(perform_experiment(qu) - k > 0) r = mid;
else l = mid;
}
qu = vector<int> (n , n);
p = r;
for(int z = 0;z <= p; ++ z) qu[z * 2 + 1] = -1;
k = perform_experiment(qu);
G[p * 2 + 1] = i;
}
}
return G;
}
return G;
}
