#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
int n;
vector<vector<int>> g;
bool sim(int a, int b) { // checks if two adj nodes share color
vector<int> qr(n, n);
qr[a] = qr[b] = -1;
int cnt = perform_experiment(qr);
if (cnt == 3) return false;
if (g[a].size() == 1 && g[b].size() == 1) {
if (cnt == 1) return true;
else return false;
}
return true;
}
vector<int> solve3() {
int comps = 0;
vector<int> q;
vector<int> cols(n);
int currCol = 0;
for (int i = 0; i < n; i++) {
cols[i] = currCol;
if (i == n-1) break;
if (sim(i, i+1)) continue;
else currCol++;
}
return cols;
}
vector<int> solve12() {
return {-1};
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n = N;
bool line = true;
g.resize(n+1);
int m = X.size();
for (int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
if (min(X[i], Y[i]) != max(X[i], Y[i]) - 1) line = false;
}
if (n <= 50 && !line) return solve12();
else if (line) solve3();
return {-1};
}
