#include "sphinx.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) cout<<#v<<": "; for(auto u : v)cout<<u<<' '; cout<<endl
#define ask(v) perform_experiment(v)
using namespace std;
std::vector<int> find_colours(int n, std::vector<int> U, std::vector<int> V) {
vi ans(n, -1); int N = n, idk = 0;
if(n%2==1){
f0r(c,n){vi quer(n,c); quer[n-1] = -1; int ret = ask(quer); if(ret == 1){ans[n-1] = c; break;}} N--, idk = 1;
}
f0r(c,n){
vi quer(n,c); for(int i = 1; i < N; i+=2)quer[i] = -1; if(n!=N)quer.back() = n;
int ret = ask(quer); ret-=idk; ret = N - ret; int cnt = ret/2 + ret%2;
int pv = N/2-1; while(cnt>0){
int lo = 0, hi = pv; while(lo < hi){
int mid = lo + (hi-lo+1) / 2; //check if [mid, N/2-1] got col c
vi quer(n,n); int bruh = 1; if(mid==0)bruh=0;
for(int i = 2*mid; i < N; i++){bruh++; if(i%2==0)quer[i] = c; else quer[i] = -1;}
int ret = ask(quer); ret -= idk; if(ret==bruh)hi=mid-1; else lo=mid;
} ans[lo*2+1] = c; pv = lo - 1; cnt--;
}
f0r(i,n)quer[i]=c; for(int i = 0; i < N; i+=2)quer[i] = -1; if(n!=N)quer.back() = n;
ret = ask(quer); ret -= idk; ret = N - ret; cnt = ret/2 + ret%2;
pv = 0; while(cnt > 0){
int lo = pv, hi = N/2-1; while(lo < hi){
int mid = lo + (hi-lo) / 2;
vi quer(n,n); int bruh = 1; for(int i = 0; i <= 2*mid+1; i++){bruh++; if(i%2==0)quer[i] = -1; else quer[i]=c;}
int ret = ask(quer); if(ret==bruh)lo=mid+1; else hi=mid;
}
ans[lo*2] = c; pv = lo + 1; cnt--;
}
}
return ans;
}
