#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>
int perform_experiment(std::vector<int> E);
class dsu {
private:
std::vector<int> par;
int n;
public:
dsu(int n) : n(n), par(n) { std::iota(par.begin(), par.end(), 0); }
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }
bool merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) {
return false;
}
par[v] = u;
return true;
}
};
std::vector<int> find_colours(int n, std::vector<int> x, std::vector<int> y) {
const int m = x.size();
auto comps = [&](int u, int v) {
dsu dsu(n);
int ans = n - 2;
for (int i = 0; i < m; ++i) {
if (x[i] != u and x[i] != v and y[i] != v and y[i] != u) {
ans -= dsu.merge(x[i], y[i]);
}
}
return ans;
};
std::vector<int> ans(n);
std::vector<bool> done(n);
for (int i = 0; i < m; ++i) {
x.push_back(y[i]);
y.push_back(x[i]);
}
for (int i = 0; i < 2 * m; ++i) {
int u = x[i], v = y[i];
if (done[u]) {
std::swap(u, v);
}
if (done[u]) {
continue;
}
for (int c = 0; c < n; ++c) {
if (done[u]) {
break;
}
std::vector<int> q(n, n);
q[u] = -1;
q[v] = c;
if (perform_experiment(q) - comps(u, v) == 1) {
ans[u] = c;
done[u] = true;
}
}
assert(done[u]);
}
return ans;
}
