#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> C, num;
void solve(int l, int r, int c, int z=-1){
if (r < l) return;
int p = (l % 2);
if (r % 2 != p) r--;
//cout << l << " " << r << " " << c << endl;
if (l == 0){
vector<int> v(N, N);
v[l] = -1;
v[l+1] = c;
if (C[l] == -1 && perform_experiment(v) < min(N, 3)){
C[l] = c;
num[c]++;
}
solve(l+2, r, c);
return;
}
if (r == N-1){
vector<int> v(N, N);
v[r] = -1;
v[r-1] = c;
if (C[r] == -1 && perform_experiment(v) < min(N, 3)){
C[r] = c;
num[c]++;
}
solve(l, r-2, c);
return;
}
int x = 0;
for (int i=l; i<=r; i++) x += (C[i] == -1);
if (x == 0) return;
vector<int> v(N, N);
for (int i=l; i<=r; i+=2) v[i] = -1;
for (int i=1-p; i<N; i+=2) v[i] = c;
if (z == -1) z = (N-perform_experiment(v))/2;
if (z == 0) return;
if (z == x){
num[c] += z;
for (int i=l; i<=r; i+=2){
if (C[i] == -1) C[i] = c;
}
return;
}
int exp = num[c]+z;
int m = (l+r)/2;
if (m % 2 != p) m--;
solve(l, m, c);
if (num[c] != exp) solve(m+2, r, c, exp-num[c]);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
::N = N;
C.resize(N, -1);
int M = X.size();
if (N <= 50){
for (int bruh=0; bruh<2*M; bruh++){
int i = bruh % M;
if (C[X[i]] == -1){
vector<int> v(N, N);
v[X[i]] = 0;
v[Y[i]] = 0;
int tar = perform_experiment(v);
for (int j=0; j<N; j++){
v[X[i]] = -1;
v[Y[i]] = j;
if (perform_experiment(v) == tar){
C[X[i]] = j;
break;
}
}
}
swap(X[i], Y[i]);
}
return C;
}
if (M == N*(N-1)/2){
for (int i=0; i<N; i++){
int l = 0, r = N;
while (l < r-1){
int m = (l+r)/2;
int cur = 0;
vector<int> v(N, -1);
for (int j=0; j<N; j++){
if (i == j) continue;
v[j] = cur;
if (cur < m-1) cur++;
}
if (perform_experiment(v) == m) r = m;
else l = m;
}
C[i] = l;
}
return C;
}
num.resize(N, 0);
for (int i=0; i<N; i++){
solve(0, N-1, i);
solve(1, N, i);
}
return C;
}
