#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 250 + 7;
int fau[N], ansclr[N];
vector<int> ed[N], ed2[N];
bool vis[N];
vector<int> dfst, vset[2];
int Find(int v)
{
if(fau[v] == v) return v;
return (fau[v] = Find(fau[v]));
}
void Union(int a, int b)
{
//cout << "Union " << a << " " << b << "\n";
a = Find(a); b = Find(b);
fau[max(a, b)] = min(a, b);
}
void DFSN2(int v)
{
vis[v] = true;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(Find(v) != Find(ed[v][i]))
ed2[Find(v)].pb(Find(ed[v][i]));
if(vis[ed[v][i]])
continue;
DFSN2(ed[v][i]);
}
}
void DFSclr(int v, int c)
{
vis[v] = true;
vset[c].pb(v);
for(int i = 0; i < (int)ed2[v].size(); ++i)
if(!vis[ed2[v][i]])
DFSclr(ed2[v][i], c ^ 1);
}
void DoNew(int n)
{
DFSN2(0);
for(int i = 0; i < n; ++i) vis[i] = false;
for(int i = 0; i < n; ++i)
{
vector<int> nw;
sort(ed2[i].begin(), ed2[i].end());
for(int j = 0; j < (int)ed2[i].size(); ++j)
if(j == 0 || ed2[i][j] != ed2[i][j - 1])
nw.pb(ed2[i][j]);
ed2[i] = nw;
}
DFSclr(0, 0);
for(int i = 0; i < n; ++i) vis[i] = false;
}
void DFS(int v)
{
vis[v] = true;
for(int i = 0; i < (int)ed[v].size(); ++i)
if((!vis[ed[v][i]]) && dfst[ed[v][i]] == dfst[v])
DFS(ed[v][i]);
}
int Sus(vector<int> que)
{
int ans = 0, n = que.size();
dfst.clear();
for(int i = 0; i < n; ++i)
if(que[i] != -1)
dfst.pb(que[i]);
else
dfst.pb(-Find(i) - 1);
for(int i = 0; i < n; ++i)
if(!vis[i])
{
++ans;
DFS(i);
}
for(int i = 0; i < n; ++i) vis[i] = false;
return ans;
}
void D1(int n)
{
vector<int> bas(n, -1), que;
for(int i = 0; i < n; ++i)
{
que = bas;
que[1] = i;
if(perform_experiment(que) == 1)
ansclr[0] = i;
}
}
void FindClr(int n)
{
vector<int> bas(n, -1), cur, que;
cur = vset[1];
//cerr << "beg " << vset[1].size() << "\n";
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < (int)vset[0].size(); ++j)
bas[vset[0][j]] = i;
for(int j = 0; j < (int)vset[1].size(); ++j)
bas[vset[1][j]] = -1;
for(int j = 0; j < n; ++j) bas[j] = bas[Find(j)];
que = bas;
//for(int j = 0; j < n; ++j)
//cout << que[j] << " ";
//cout << "\n";
int ant = Sus(que);
int akt = perform_experiment(que);
int il = ant - akt;
//cerr << "Clr: " << i << " " << ant << " " << akt << "\n";
while(il > 0)
{
int p = 0, s, k = (int)cur.size() - 1;
while(p < k)
{
s = (p + k) / 2;
que = bas;
for(int j = s + 1; j < (int)cur.size(); ++j)
que[cur[j]] = n;
for(int j = 0; j < n; ++j) que[j] = que[Find(j)];
int abc = Sus(que);
if(perform_experiment(que) < abc)
k = s;
else
p = s + 1;
}
//if(cur.size() == 0) return;
//cerr << "F: " << cur[p] << " " << il << "\n";
que = bas;
//for(int j = 0; j < n; ++j)
//cerr << que[j] << " ";
//cout << "\n";
int xd = Sus(que);
que[cur[p]] = i;
for(int j = 0; j < n; ++j) que[j] = que[Find(j)];
/*for(int j = 0; j < n; ++j)
cerr << que[j] << " ";
cerr << "\n";*/
int xd2 = Sus(que);
//cerr << xd << " " << xd2 << "\n";
il -= (xd - xd2);
ansclr[cur[p]] = i;
bas[cur[p]] = i;
for(int j = 0; j < n; ++j) bas[j] = bas[Find(j)];
vector<int> nw;
for(int j = 0; j < (int)cur.size(); ++j)
if(j != p)
nw.pb(cur[j]);
cur = nw;
}
}
}
void FN(int v, int il, int n)
{
vector<int> cur, bas(n, n), que, ss;
for(int i = 0; i < (int)ed[v].size(); ++i)
if(!vis[Find(ed[v][i])] && ed[v][i] < v)
{
cur.pb(Find(ed[v][i]));
vis[cur.back()] = true;
}
for(int i = 0; i < (int)cur.size(); ++i)
vis[cur[i]] = false;
while(il--)
{
int p = 0, s, k = cur.size() - 1;
while(p < k)
{
s = (p + k) / 2;
que = bas;
for(int i = 0; i <= s; ++i)
que[cur[i]] = -1;
que[v] = -1;
for(int i = 0; i < n; ++i) que[i] = que[Find(i)];
int ans = perform_experiment(que);
int ant = Sus(que);
if(ans < ant)
k = s;
else
p = s + 1;
}
ss.pb(cur[p]);
vector<int> nw;
for(int i = p + 1; i < (int)cur.size(); ++i) nw.pb(cur[i]);
cur = nw;
}
for(int i = 0; i < (int)ss.size(); ++i)
Union(v, ss[i]);
}
vector<int> find_colours(int _N, vector<int> _X, vector<int> _Y)
{
int n = _N;
vector<int> answer;
for(int i = 0; i < (int)_X.size(); ++i)
{
ed[_X[i]].pb(_Y[i]);
ed[_Y[i]].pb(_X[i]);
}
vector<int> cq(n, n);
for(int i = 0; i < n; ++i)
fau[i] = i;
cq[0] = -1;
for(int i = 1; i < n; ++i)
{
cq[i] = -1;
int akt = perform_experiment(cq);
int ant = Sus(cq);
//cerr << "F:\n";
//for(int j = 0; j < n; ++j)
//cerr << Find(j) << " ";
//cout << "\n";
//cerr << "Sp: " << i << " " << akt << " " << ant << "\n";
FN(i, ant - akt, n);
}
DoNew(n);
if((int)vset[1].size() == 0)
D1(n);
else
{
FindClr(n);
swap(vset[1], vset[0]);
FindClr(n);
}
for(int i = 0; i < n; ++i)
answer.pb(ansclr[Find(i)]);
return answer;
}
