#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
bool BEGIN_ALLOC;
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) FOR(i, 0, r)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
map<vi, int> askedQueries;
int query(vi E){
return perform_experiment(E);
}
vi find_colours12(int N, vi X, vi Y){
vi base(N, -1);
vi ans(N);
F0R(i, N){
vi p(N);
iota(all(p), 0);
shuffle(all(p), mt19937(12310123123));
for(auto c : p){
fill(all(base), c);
base[i] = -1;
if(query(base) == 1){
ans[i] = c;
break;
}
}
}
return ans;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
// if(N <= 50) return find_colours12(N, X, Y);
vector<vi> adj(N);
int M = sz(X);
F0R(i, M){
adj[X[i]].eb(Y[i]);
adj[Y[i]].eb(X[i]);
}
//Step 1 : Detect monochromatic components
vector<vi> components;
vi insertOrder(N);
iota(all(insertOrder), 0);
shuffle(all(insertOrder), mt19937(10210312));
vi vis(N);
function<void(int, vi&)> dfs = [&](int u, vi& E){
vis[u] = true;
for(auto v : adj[u]) if(!vis[v] && E[v] == N){
dfs(v, E);
}
};
auto countAdjacentNComponents = [&](int start, vi& E){
fill(all(vis), false);
int cnt = 0;
for(auto i : adj[start]) if(!vis[i] && E[i] == N){
++cnt;
dfs(i, E);
}
return cnt;
};
auto countNComponents = [&](vi& E){
fill(all(vis), false);
int cnt = 0;
F0R(i, N) if(!vis[i] && E[i] == N){
++cnt;
dfs(i, E);
}
return cnt;
};
auto countKnownComponents = [&](vi& E){
// cerr << "countKnownComps : \n";
// for(auto u : E) cerr << u << " "; cerr << '\n';
// cerr << '\n';
fill(all(vis), false);
int cnt = 0;
F0R(i, N) if(!vis[i] && E[i] != -1){
function<void(int)> rec = [&](int u){
vis[u] = true;
for(auto v : adj[u]) if(!vis[v] && E[v] == E[i]){
rec(v);
}
};
++cnt;
rec(i);
}
// cerr << "== " << cnt << '\n';
return cnt;
};
for(auto u : insertOrder){
if(components.empty()){
vi nw = {u};
components.eb(nw);
continue;
}
auto check = [&](int l, int r){
vi E(N, N);
FOR(i, l, r + 1){
for(auto u : components[i]) E[u] = -1;
}
int base = countNComponents(E) + (r - l + 1);
E[u] = -1;
int cnt = countAdjacentNComponents(u, E);
int added = query(E);
int ifNew = base + cnt;
return ifNew != added;
};
vi marked(sz(components)), mergedComponent = {u};
int l = 0, r = sz(components) - 1;
while(l <= r && check(l, r)){
int backEdge = -1;
int lo = l, hi = r;
while(lo <= hi){
int mid = lo + hi >> 1;
bool ok = check(l, mid);
// cerr << mid << " : " << ok << '\n';
if(ok) backEdge = mid, hi = mid - 1;
else lo = mid + 1;
}
if(backEdge == -1) break;
marked[backEdge] = 1;
mergedComponent.insert(mergedComponent.end(), all(components[backEdge]));
l = backEdge + 1;
}
vector<vi> newComponents;
F0R(i, sz(components)) if(!marked[i]){
newComponents.pb(components[i]);
}
newComponents.pb(mergedComponent);
swap(components, newComponents);
}
if(sz(components) == 1){
F0R(i, N){
vi E(N, -1);
E[0] = i;
if(perform_experiment(E) == 1) return vi(N, i);
}
assert(false);
}
#ifdef LOCAL
checkPoint("first phase finished !");
#endif //LOCAL
int cnt = 0;
//Compress the monochromatic components into super-vertexes and create the induced graph G'
//In G', every edge (u, v) has the property C[u] != C[v] (u, v are both super-vertexes)
vi superVertexIdx(N);
for(auto comp : components){
for(auto u : comp) superVertexIdx[u] = cnt;
++cnt;
}
int superNodes = sz(components);
vector<vi> adjSuper(superNodes);
F0R(i, M){
int x = X[i], y = Y[i];
x = superVertexIdx[x]; y = superVertexIdx[y];
if(x != y){
adjSuper[x].eb(y);
adjSuper[y].eb(x);
}
}
vi A, B;
function<void(int, int)> distribute = [&](int u, int c){
(c ? B : A).pb(u);
vis[u] = 1;
// cerr << u << ' ' << c << '\n';
for(auto v : adjSuper[u]) if(!vis[v]){
distribute(v, c ^ 1);
}
};
fill(all(vis), false);
distribute(0, 0);
//Step 2 : Detect original colors
auto colorSupervertex = [&](vi& E, int u, int c){
// cerr << "color " << u << ' ' << c << '\n';
for(auto x : components[u]) E[x] = c;
};
vi ans(N);
F0R(_, 2){
// cerr << "\nthis turn\n";
// cerr << "A = "; for(auto u : A) cerr << u << ' '; cerr << '\n';
// cerr << "B = "; for(auto u : B) cerr << u << ' '; cerr << '\n';
F0R(x, N){
// cerr << "current = " << x << '\n';
vi E(N, -1);
for(auto u : B) colorSupervertex(E, u, x);
auto check = [&](int l, int r){
// cerr << "check " << l << ' ' << r << '\n';
vi tmp = E;
F0R(i, l) colorSupervertex(tmp, A[i], N);
FOR(i, r + 1, sz(A)) colorSupervertex(tmp, A[i], N);
int cur = query(tmp);
int bound = countKnownComponents(tmp);
// for(auto x : tmp) cerr << x << ' '; cerr << '\n';
// cerr << "=> " << cur << " | " << bound + (r - l + 1) << '\n';
return cur != (bound + r - l + 1);
};
int l = 0, r = sz(A) - 1;
while(l <= r && check(l, r)){
// if(l == 0){
// cerr << "A has color " << x << '\n';
// }
int lo = l, hi = r, first = -1;
while(lo <= hi){
int mid = lo + hi >> 1;
if(check(l, mid)) first = mid, hi = mid - 1;
else lo = mid + 1;
}
if(first == -1) break;
for(auto u : components[A[first]]){
ans[u] = x;
// cerr << "declare that " << u << " has color = " << x << '\n';
}
l = first + 1;
}
// cerr << '\n';
}
swap(A, B);
// cerr << '\n';
}
#ifdef LOCAL
checkPoint("second phase finished !");
#endif //LOCAL
return ans;
}
