#include "sphinx.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
int n;
vi graph[251];
int my_root[251];
vi graph2[251];
int dist[251];
bool odw[251];
bool is_in[251];
vi my_verts[251];
int fint(int v)
{
if(my_root[v] == v) return v;
my_root[v] = fint(my_root[v]);
return my_root[v];
}
void onion(int a, int b)
{
a = fint(a);
b = fint(b);
my_root[a] = b;
}
void dfs(int v, int d)
{
odw[v] = 1;
dist[v] = d;
forall(it,graph2[v])
{
if(odw[it] == 0)
{
dfs(it,(d+1)%2);
}
}
}
vi ans;
void dfs_comp(int v)
{
odw[v] = 1;
forall(it,graph[v])
{
if(odw[it] == 0 && is_in[it]) dfs_comp(it);
}
}
bool check_comps(vi& c0, int color)
{
rep(i,n) odw[i] = 0;
rep(i,n) is_in[i] = 1;
vi query(n,color);
forall(it,c0) forall(it2,my_verts[it]) query[it2] = -1;
forall(it,c0) forall(it2,my_verts[it]) is_in[it2] = 0;
set<int> dif;
forall(it,c0) dif.insert(fint(it));
int comps = siz(dif);
rep(i,n)
{
if(odw[i] == 0 && is_in[i])
{
comps++;
dfs_comp(i);
}
}
return perform_experiment(query) != comps;
}
int sons_cnt(vi r, int v)
{
rep(i,n) odw[i] = 0;
rep(i,n) is_in[i] = 1;
vi query(n,n);
query[v] = -1;
is_in[v] = 0;
forall(it,r) query[it] = -1;
forall(it,r) is_in[it] = 0;
int comps = siz(r)+1;
rep(i,n)
{
if(odw[i] == 0 && is_in[i] == 1)
{
comps++;
dfs_comp(i);
}
}
return comps-perform_experiment(query);
}
void solve(set<int> c0)
{
rep(color,n)
{
while(true)
{
vi rest;
forall(it,c0) rest.pb(it);
if(!check_comps(rest,color)) break;
int l = 0;
int r = siz(rest)-1;
while(l < r)
{
vi rest2;
rep2(i,l,(l+r)/2) rest2.pb(rest[i]);
if(check_comps(rest2,color)) r = (l+r)/2;
else l = (l+r)/2+1;
}
int root = fint(rest[l]);
rep(i,n)
{
if(fint(i) == root)
{
ans[i] = color;
}
}
c0.erase(c0.find(root));
}
}
}
vi find_colours(int N, vi X, vi Y)
{
n = N;
ans.resize(n,-1);
rep(i,n) my_root[i] = i;
rep(i,siz(X))
{
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
rep(i,n)
{
int cnt = 1;
set<int> comps;
vi ro2;
forall(it,graph[i])
{
if(it < i && comps.find(fint(it)) == comps.end())
{
comps.insert(fint(it));
ro2.pb(it);
cnt++;
}
}
int sons = sons_cnt(ro2,i);
if(sons == 0) continue;
else
{
rep(j,sons)
{
vi ro;
forall(it,ro2)
{
if(fint(it) != fint(i))
{
ro.pb(it);
}
}
int l = 0;
int r = siz(ro)-1;
while(l < r)
{
vi r2;
rep2(i,l,(l+r)/2) r2.pb(ro[i]);
if(sons_cnt(r2,i) != 0) r = (l+r)/2;
else l = (l+r)/2+1;
}
onion(i,ro[l]);
}
}
}
rep(i,n)
{
forall(it,graph[i])
{
graph2[fint(i)].pb(fint(it));
}
}
int roots_cnt = 0;
rep(i,n) odw[i] = 0;
rep(i,n)
{
if(fint(i) == i)
{
dfs(i,0);
break;
}
}
rep(i,n)
{
my_verts[fint(i)].pb(i);
if(fint(i) == i)
{
roots_cnt++;
}
}
if(roots_cnt == 1)
{
rep(i,n)
{
vi query(n,-1);
query[0] = i;
if(perform_experiment(query) == 1)
{
rep(j,n)
{
ans[j] = i;
}
break;
}
}
return ans;
}
set<int> s[2];
rep(i,n)
{
if(fint(i) == i)
{
s[dist[i]].insert(i);
}
}
solve(s[0]);
solve(s[1]);
return ans;
}
