#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int n;
vector<bool> visited, ina, inb;
vector<int> col, a(1, -1), b(1, -1);
vector<vector<int> > graph, fgraph;
void dfs(int node){
visited[node]=1;
for (auto num:graph[node])if (!visited[num]&&col[num]==col[node])dfs(num);
}
int calc(){
visited.assign(n, 0);
int c=0;
for (int i=0; i<n; ++i)if (!visited[i])dfs(i), ++c;
return c;
}
void dfs2(int node, int t){
visited[node]=1;
if (t)a.pb(node), ina[node]=1;
else b.pb(node), inb[node]=1;
for (auto num:fgraph[node])if (!visited[num])dfs2(num, !t);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
n=N;
col.resize(n, n);
ina.resize(n, 0);
inb.resize(n, 0);
fgraph.resize(n);
graph.resize(n);
vector<int> rel(n, n), real(n, -1), ans(n);
for (int i=0; i<X.size(); ++i){
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
for (int i=0; i<n; ++i){
vector<int> temp(n);
temp[i]=-1;
col[i]=n-1;
for (int j=0; j<i; ++j)temp[j]=-1, col[j]=rel[j];
for (int j=i+1; j<n; ++j)temp[j]=col[j]=n;
int res=calc(), res2=perform_experiment(temp);
if (res==res2){
rel[i]=i;
continue;
}
set<int> merge;
for (int loop=0, p=-1; loop<res-res2; ++loop){
int low=p, high=i-1;
while (low+1<high){
int mid=(low+high)/2;
for (int j=0; j<n; ++j){
if (low<rel[j]&&rel[j]<=mid)temp[j]=-1, col[j]=rel[j];
else temp[j]=n, col[j]=n;
}
col[i]=n-1;
temp[i]=-1;
if (calc()==perform_experiment(temp))low=mid;
else high=mid;
}
merge.insert(high);
p=high;
}
rel[i]=*merge.begin();
for (int j=0; j<n; ++j)if (merge.find(rel[j])!=merge.end())rel[j]=*merge.begin();
}
for (int i=0; i<X.size(); ++i)if (rel[X[i]]!=rel[Y[i]]){
fgraph[rel[X[i]]].pb(rel[Y[i]]);
fgraph[rel[Y[i]]].pb(rel[X[i]]);
}
visited.assign(n, 0);
dfs2(rel[0], 0);
if (b.empty()){
for (int i=0; i<n; ++i){
vector<int> temp(n, -1);
temp[0]=i;
if (perform_experiment(temp)==1){
for (int j=0; j<n; ++j)ans[j]=i;
return ans;
}
}
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int loop=0; loop<2; ++loop, swap(a, b), swap(ina, inb))for (int i=0; i<n; ++i){
while(a.size()){
vector<int> temp(n);
for (int j=0; j<n; ++j){
if (ina[rel[j]])temp[j]=-1, col[j]=rel[j];
else temp[j]=i, col[j]=n;
}
int res=calc(), res2=perform_experiment(temp);
if (res==res2)break;
int low=0, high=a.size();
while (low+1<high){
int mid=(low+high)/2;
for (int j=0; j<n; ++j){
if (ina[rel[j]]&&a[low]<rel[j]&&rel[j]<=a[mid])temp[j]=-1, col[j]=rel[j];
else temp[j]=i, col[j]=n;
}
if (calc()==perform_experiment(temp))low=mid;
else high=mid;
}
swap(a[high], a[a.size()-1]);
ina[a.back()]=0;
real[a.back()]=i;
a.pop_back();
sort(a.begin(), a.end());
}
}
for (int i=0; i<n; ++i)ans[i]=real[rel[i]];
return ans;
}
