#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
//////////////////////////////////////////////////////////////////
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
auto n = N, m = (int)X.size();
auto x = X, y = Y;
vector<int> col(n, 0);
for (int i = 0; i < n; i++)
col[i] = i;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++)
graph[x[i]].push_back(y[i]),
graph[y[i]].push_back(x[i]);
function<int(int)> fnd = [&](int x)
{
if (col[x] == x)
return x;
return col[x] = fnd(col[x]);
};
{
auto povezan = [&](vector<int> tuff, int idx)
{
vector<int> salji(n, n);
for (int i : tuff)
salji[i] = -1;
vector<bool> vis(n, 0);
function<void(int)> dfs = [&](int cur)
{
if (vis[cur] || salji[cur] != n)
return;
vis[cur] = 1;
for (int a : graph[cur])
dfs(a);
};
salji[idx] = -1;
set<int> dif;
for (int i : tuff)
dif.insert(fnd(col[i]));
int comps = dif.size();
for (int i = 0; i < n; i++)
if (!vis[i] && salji[i] == n)
{
comps++;
dfs(i);
}
return perform_experiment(salji) <= comps;
};
vector<int> pref;
pref.push_back(0);
for (int i = 1; i < n; i++)
{
if (povezan(pref, i))
{
set<int> used;
vector<int> space;
for (int a : graph[i])
if (a < i && used.count(fnd(a)) == 0)
space.push_back(a), used.insert(col[a]);
sort(space.begin(), space.end());
int k = space.size();
auto fnd_next = [&](int cur)
{
int bg = lower_bound(space.begin(), space.end(), cur) - space.begin();
int l = bg;
int r = k;
auto check = [&](int bnd)
{
if (bnd == k)
return true;
vector<int> src;
for (int j = bg; j <= bnd; j++)
src.push_back(space[j]);
return povezan(src, i);
};
if (!check(k-1))
return k;
while (r - l)
{
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
return l;
};
int cur = fnd_next(0);
while (cur < k)
{
col[fnd(space[cur])] = i;
cur = fnd_next(space[cur] + 1);
}
}
pref.push_back(i);
}
for (int i = 0; i < n; i++)
col[i] = fnd(i);
}
vector<int> ans(n,n-1);
int isti = 0;
{
set<int> difs;
for (int i = 0; i < n; i++)
difs.insert(fnd(i));
isti = difs.size();
}
vector<vector<int>> cols(n);
for (int i = 0; i < n; i++)
cols[fnd(i)].push_back(i);
if (isti == 1){
vector<int> salji(n,n);
vector<int> ales;
for (int c = 0; c < n; c++)
{
salji.assign(n,c);
salji[0] = -1;
ales.push_back(perform_experiment(salji));
}
ans[fnd(0)] = min_element(ales.begin(),ales.end())-ales.begin();
}
else
{
vector<vector<int>> g(n);
for (int i = 0; i < m; i++)
{
if (fnd(x[i]) == fnd(y[i]))continue;
g[fnd(x[i])].push_back(fnd(y[i]));
g[fnd(y[i])].push_back(fnd(x[i]));
}
vector<int> bi(n,-1);
function<void(int,int)> bic = [&](int cur,int prev)
{
bi[cur] = 1-bi[prev];
for (int a : g[cur])
if (bi[a]<0)
bic(a,cur);
};
bi[fnd(0)] = 1;
bic(fnd(0),fnd(0));
vector<int> a,b;
for (int i = 0; i < n; i++)
if (bi[fnd(i)])
a.push_back(fnd(i));
else
b.push_back(fnd(i));
sort(a.begin(),a.end());
sort(b.begin(),b.end());
a.resize(unique(a.begin(),a.end())-a.begin());
b.resize(unique(b.begin(),b.end())-b.begin());
for (int it = 0;it < 2; it++)
{
int p = a.size(),q = b.size();
vector<bool> vis(n,0);
vector<int> salji(n,0);
function<void(int,int)> cntc = [&](int cur,int c)
{
if (vis[cur])return;
vis[cur] = 1;
for(auto a : graph[cur])
if (salji[a] == c)
cntc(a,c);
};
auto check = [&](vector<int> tuff, int c)
{
vis.assign(n,0);
salji.assign(n,n);
for (int i : b)
for (int x : cols[i])
salji[x] = c;
for (int i : tuff)
for (int x : cols[i])
salji[x] = -1;
int comps = 0;
for (int i = 0; i < n; i++)
{
if (!vis[i] && salji[i] == n)
{
comps++;
cntc(i,n);
}
}
for (int i = 0; i < n; i++)
{
if (!vis[i] && salji[i] == c)
{
comps++;
cntc(i,c);
}
}
set<int> difs;
for (int i = 0; i < n; i++)
if (salji[i] == -1)
difs.insert(fnd(i));
comps+=difs.size();
return perform_experiment(salji) < comps;
};
auto fnd_nxt = [&](int cur,int c)
{
vector<int> koji;
vector<int> v;
for (int i = 0; i < p; i++)
if (ans[a[i]] == n-1)
v.push_back(a[i]),koji.push_back(i);
int sz = v.size();
int bg = lower_bound(v.begin(),v.end(),cur)-v.begin();
auto salji = [&](int idx)
{
vector<int> tuf;
if (idx == sz)return true;
for (int i = bg; i <= idx; i++)
tuf.push_back(v[i]);
return check(tuf,c);
};
if (!salji(sz-1)) return p;
int l = bg,r = sz;
while(r-l)
{
int mid = l+r>>1;
if (salji(mid))
r = mid;
else
l = mid+1;
}
if (r==sz)return p;
return koji[l];
};
for (int c = 0; c < n-1; c++)
{
int cur = fnd_nxt(0,c);
while(cur < p)
{
ans[a[cur]] = c;
cur = fnd_nxt(a[cur]+1,c);
}
}
swap(a,b);
}
}
for (int i = 0; i < n; i++)
col[i] = ans[fnd(i)];
return col;
}
///////////////////////////////////////////////////////////////////
