#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
void trace_vec(vi &inp) {
for (auto &el : inp) cout << el << " ";
cout << "\n";
}
int N, M;
vector<set<int>> adj;
vi G;
int queryTwo(int a, int b, int colourA, int colourB) {
vi E(N, N);
E[a] = colourA;
E[b] = colourB;
return perform_experiment(E);
}
void findColour(int a) {
if (G[a] != -1) return;
int neighbour = *adj[a].begin();
int b2 = queryTwo(a, neighbour, 0, 0);
int baseline = queryTwo(a, neighbour, -1, -1);
bool same = baseline == b2;
for (int colour = 0; colour < N; colour++) {
int x1 = queryTwo(a, neighbour, colour, -1);
int x2 = queryTwo(a, neighbour, -1, colour);
if (same && b2 == x1) {
G[a] = G[neighbour] = colour;
return;
}
if (!same && x1 == b2) {
G[neighbour] = colour;
}
if (!same && x2 == b2) {
G[a] = colour;
}
}
}
void findFrom(int a, int b) {
if (G[a] == -1) return;
if (G[b] != -1) return;
if (adj[a].count(b) == 0) return;
int baseline = queryTwo(a, b, -1, -1);
for (int colour = 0; colour < N; colour++) {
int x = queryTwo(a, b, colour, -1);
if (x < baseline) {
G[b] = colour;
break;
} else if (x > baseline) {
G[b] = G[a];
break;
}
}
}
vi find_colours(int _N, vi X, vi Y) {
N = _N, M = (int) X.size();
adj.assign(N, set<int>());
for (int i = 0; i < M; i++) {
adj[X[i]].insert(Y[i]);
adj[Y[i]].insert(X[i]);
}
bool path = M == N - 1 && adj[0] == set<int>({1}) && adj[N - 1] == set<int>({N - 2});
for (int i = 1; i < N - 1; i++) {
path = path && adj[i] == set<int>({i - 1, i + 1});
}
G.assign(N, -1);
if (N == 2) { // 3/100 pts
findColour(0);
return G;
} else if (N <= 50) {
set<int> vis;
queue<int> q;
q.push(0);
findColour(0);
while (!q.empty()) {
int cur = q.front();
q.pop();
// cout << "visited " << cur << "\n";
vis.insert(cur);
for (int v : adj[cur]) {
if (vis.count(v)) continue;
findFrom(cur, v);
q.push(v);
}
// cout << "colour is: " << G[cur] << "\n";
}
return G;
} else if (path) {
G[0] = 0;
G[1] = queryTwo(0, 1, -1, -1) == 2 ? G[0] : 1 - G[0];
for (int i = 2; i < N - 1; i++) {
G[i] = queryTwo(i - 1, i, -1, -1) == 3 ? G[i - 1] : 1 - G[i - 1];
}
G[N - 1] = queryTwo(N - 2, N - 1, -1, -1) == 2 ? G[N - 2] : 1 - G[N - 2];
return G;
} else if (M == (N * (N - 1) / 2)) {
return G;
}
return G;
}
