#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
int n = N, m = (int)X.size();
vector<int> x = X, y = Y;
vector<int> par(n), sz(n, 1);
iota(par.begin(), par.end(), 0);
auto find = [&](auto self, int u) -> int
{
return par[u] = (par[u] == u ? u : self(self, par[u]));
};
auto unite = [&](int u, int v) -> bool
{
u = find(find, u);
v = find(find, v);
if(u == v)
return false;
if(sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
par[u] = v;
return true;
};
vector adj(n, vector<int>());
for(int i = 0; i < m; i++)
{
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
for(auto &i: adj)
sort(i.begin(), i.end());
vector<bool> vis(n, false);
vector<int> e(n, n);
vector<int> res(n, 0);
int curr = -1;
int cnt = 1;
int lst = 0;
/*queue<tuple<int, int, int, int>> q;
q.push({0, -1, -1, 1});
int ss = 0;
while(not q.empty())
{
auto [u, p, m, c] = q.front();
q.pop();
if(vis[u])
continue;
ss++;
vis[u] = true;
e[u] = -1;
int x = perform_experiment(e);
if(ss == n)
{
if(x == c - 1)
{
res[u] = m;
unite(u, p);
}
else
{
res[u] = ++m;
c++;
}
break;
}
if(x == c)
{
res[u] = m;
unite(u, p);
}
else
{
res[u] = ++m;
c++;
}
for(auto i: adj[u])
{
if(vis[i])
continue;
q.push({i, u, m, c});
}
}
return res;*/
/*int ss = 0;
auto dfs = [&](auto self, int u, int m, int c) -> void
{
vis[u] = true;
e[u] = -1;
int x = perform_experiment(e);
ss++;
if(ss == n)
{
if(x == cnt - 1)
{
//res[u] = m;
unite(lst, u);
}
//else
//res[u] = ++m;
return;
}
if(x == cnt)
{
//res[u] = m;
unite(lst, u);
}
else
{
//res[u] = ++m;
cnt++;
}
for(auto i: adj[u])
{
if(vis[i])
continue;
lst = u;
e[i] = -1;
self(self, i, m, c);
e[i] = n;
}
};
dfs(dfs, 0, -1, 1);*/
/// Todo: finding cycles and connect the vertices using this cycles
for(int i = 0; i < n; i++)
{
e.assign(n, n);
e[i] = -1;
vis[i] = true;
for(auto j: adj[i])
{
if(vis[j])
continue;
vis[j] = true;
e[j] = -1;
int x = perform_experiment(e);
int z = (int)adj[i].size() + (int)adj[j].size() - 2;
// cout << i << ' ' << j << ' ' << z << '\n';
if(n == 2)
{
if(x == 1)
unite(i, j);
}
else if(x == 2)
unite(i, j);
e[j] = n;
}
}
set<int> st;
map<int, int> mp;
curr = 0;
for(int i = 0; i < n; i++)
{
if(st.find(find(find, i)) == st.end())
{
st.insert(find(find, i));
mp[find(find, i)] = res[i] = curr++;
}
else
{
res[i] = mp[find(find, i)];
}
}
return res;
/*for(int i = 0; i < n; i++)
{
e.assign(n, -1);
for(int j = 0; j < n; j++)
{
for(int k = 0; k < n; k++)
{
if(k == i)
continue;
e[k] = j;
}
int m = perform_experiment(e);
if(m == 1)
{
res[i] = j;
break;
}
}
}
return res;*/
}
