#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
ll _ = 0;
int count_components(ll N, vector<vector<ll>> &adj, const std::vector<int>& colors) {
int components_cnt = 0;
std::vector<bool> vis(N, false);
for (int i = 0; i < N; i++) {
if (vis[i])
continue;
components_cnt++;
std::queue<int> q;
vis[i] = true;
q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nxt : adj[cur])
if (!vis[nxt] && colors[nxt] == colors[cur]) {
vis[nxt] = true;
q.push(nxt);
}
}
}
return components_cnt;
}
ll expected(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r, set<ll> &exc) {
vector<int> query(n, n);
for (ll i = l; i <= r; i++) if (!exc.count(nodes[i])) query[nodes[i]] = 0;
return count_components(n, adj, query);
}
ll ask(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r, ll col) {
vector<int> query(n, col);
for (ll i = l; i <= r; i++) query[nodes[i]] = -1;
return perform_experiment(query);
}
map<pll, ll> mem;
ll ask_sphinx(ll n, vector<vector<ll>> &adj, vector<ll> &nodes, ll l, ll r) {
if (l == r) {
vector<int> colors(n, n);
colors[nodes[l]] = 0;
return count_components(n, adj, colors);
}
if (mem.count({l, r})) return mem[{l, r}];
return mem[{l, r}] = ask(n, adj, nodes, l, r, n);
}
void solve_red(ll n, vector<vector<ll>> &adj, vector<int> &res, vector<ll> &red) {
vector<ll> nodes;
for (ll i = 0; i < n; i++) if (red[i]) nodes.push_back(i);
for (ll col = 0; col < n; col++) {
set<ll> exc;
ll _start = expected(n, adj, nodes, 0, nodes.size()-1, exc);
ll start = ask(n, adj, nodes, 0, nodes.size()-1, col);
while (start != _start) {
ll l = 0, r = nodes.size()-1;
while (l < r) {
ll mid = l + (r - l) / 2;
ll _q = expected(n, adj, nodes, l, mid, exc);
ll q = ask(n, adj, nodes, l, mid, col);
if (q != _q) r = mid;
else l = mid + 1;
}
res[nodes[l]] = col;
exc.insert(nodes[l]);
_start = expected(n, adj, nodes, 0, nodes.size()-1, exc);
}
}
}
void solve_blue(ll n, vector<vector<ll>> &adj, vector<int> &res, vector<ll> &red) {
vector<ll> nodes;
for (ll i = 0; i < n; i++) if (red[i]) nodes.push_back(i);
for (ll col = 0; col < n; col++) {
vector<ll> exc;
//ll _start = ask_sphinx(n, adj, nodes, 0, nodes.size()-1, exc);
ll start = ask(n, adj, nodes, 0, nodes.size()-1, col);
//while (start != _start) {
ll l = 0, r = nodes.size()-1;
while (l < r) {
ll mid = l + (r - l) / 2;
//ll _q = ask_sphinx(n, adj, nodes, l, mid, exc);
ll q = ask(n, adj, nodes, l, mid, col);
//if (q != _q) r = mid;
//else l = mid + 1;
}
res[l] = col;
exc.push_back(l);
//_start = ask_sphinx(n, adj, nodes, 0, nodes.size()-1, exc);
//}
}
}
vector<int> find_colours(int n, vector<int> u, vector<int> v) {
int m = u.size();
vector<vector<ll>> adj(n);
for (ll i = 0; i < m; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<ll> red(n);
for (ll i = 0; i < n; i++) {
red[i] = true;
for (auto &e : adj[i]) if (red[e]) red[i] = false;
}
vector<int> res(n, -1);
solve_red(n, adj, res, red);
for (auto &e : red) e = !e;
solve_red(n, adj, res, red);
//solve_blue(n, adj, res, red);
return res;
}
#ifdef TEST
#include "grader.cpp"
#endif
