#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> p, X, Y;
int find(int a){
if (a == p[a]) return p[a];
return p[a] = find(p[a]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
p[b] = a;
}
int cnt(vector<int> E){
int N = E.size(), M = X.size();
for (int i=0; i<N; i++) p[i] = i;
int res = N;
for (int i=0; i<M; i++){
if (E[X[i]] == E[Y[i]] && find(X[i]) != find(Y[i])){
res--;
merge(X[i], Y[i]);
}
}
return res;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
::X = X;
::Y = Y;
p.resize(N);
vector<int> cc(N, -1);
for (int i=0; i<N; i++){
cc[i] = i;
if (i == 0) continue;
vector<int> E1(N, N), E2(N, N);
for (int j=0; j<=i; j++){
E1[j] = cc[j];
E2[j] = -1;
}
int exp = cnt(E1), act = perform_experiment(E2);
while (exp > act){
int l = 0, r = i;
while (l != r-1){
int m = (l+r)/2;
for (int j=0; j<=i; j++){
if (cc[j] < m){
E1[j] = N;
E2[j] = N;
}
else {
E1[j] = cc[j];
E2[j] = -1;
}
}
if (cnt(E1) != perform_experiment(E2)) l = m;
else r = m;
}
for (int j=0; j<i; j++){
if (cc[j] == l) cc[j] = i;
}
exp--;
}
}
vector<int> cn(N, -1);
set<int> s;
for (int i=0; i<N; i++) s.insert(cc[i]);
int nc = s.size();
for (int i=0; i<nc; i++){
cn[*s.begin()] = i;
s.erase(s.begin());
}
for (int i=0; i<N; i++) cc[i] = cn[cc[i]];
if (nc == 1){
for (int i=0; i<N; i++){
vector<int> E2(N, i);
E2[0] = -1;
if (perform_experiment(E2) == 1){
vector<int> res(N, i);
return res;
}
}
}
vector<vector<int>> G(nc, vector<int>(nc, 0));
int M = X.size();
for (int i=0; i<M; i++){
if (cc[X[i]] == cc[Y[i]]) continue;
G[cc[X[i]]][cc[Y[i]]] = 1;
G[cc[Y[i]]][cc[X[i]]] = 1;
}
vector<int> seen(nc, -1);
stack<pair<int,int>> dfs;
dfs.push({0, 0});
while (!dfs.empty()){
int cur = dfs.top().first, par = dfs.top().second;
dfs.pop();
if (seen[cur] != -1) continue;
seen[cur] = par;
for (int next=0; next<nc; next++){
if (G[cur][next]) dfs.push({next, 1-par});
}
}
vector<int> cl(nc, -1);
for (int par=0; par<2; par++){
for (int i=0; i<N; i++){
vector<int> E1(N, i), E2(N, i);
for (int j=0; j<N; j++){
if (seen[cc[j]] == par){
if (cl[cc[j]] == -1){
E1[j] = 2*N+cc[j];
E2[j] = -1;
}
else {
E1[j] = i;
E2[j] = i;
}
}
}
int act = perform_experiment(E2);
while (cnt(E1) != act){
int l = 0, r = nc;
while (l != r-1){
int m = (l+r)/2;
for (int j=0; j<N; j++){
if (seen[cc[j]] == par){
if (cl[cc[j]] == -1 && cc[j] < m){
E1[j] = 2*N+cc[j];
E2[j] = -1;
}
else {
E1[j] = i;
E2[j] = i;
}
}
}
if (perform_experiment(E2) == cnt(E1)) l = m;
else r = m;
}
cl[l] = i;
for (int j=0; j<N; j++){
if (seen[cc[j]] == par){
if (cl[cc[j]] == -1) E1[j] = 2*N+cc[j];
else E1[j] = i;
}
}
}
}
}
vector<int> res(N);
for (int i=0; i<N; i++) res[i] = cl[cc[i]];
return res;
}
