#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>x, y;
namespace sub12{
vector<int>solve(){
vector<int>ans(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
vector<int>c(n, j);
c[i] = -1;
if(perform_experiment(c) == 1){
ans[i] = j;
break;
}
}
}
return ans;
}
}
namespace sub3{
bool check_subtask(){
if(m != n - 1){
return false;
}
for(int i = 0; i < m; i++){
if(y[i] != x[i] + 1){
return false;
}
}
return true;
}
vector<int>solve(){
vector<int>part(n), ans(n);
int N = 0;
for(int i = ans[0] = 0; i + 1 < n; i++){
vector<int>c(n, n);
c[i] = c[i + 1] = -1;
if(perform_experiment(c) > 2 + int(i != 0 && i + 2 != n)){
N++;
}
part[i + 1] = N;
}
if(N == 0){
for(int c = 0; c < n; c++){
fill(ans.begin(), ans.end(), -1);
ans[0] = c;
if(perform_experiment(ans) == 1){
fill(ans.begin(), ans.end(), c);
break;
}
}
return ans;
}
for(int c = 0; c < n; c++){
for(int z = 0; z < 2; z++){
vector<int>color(n, -1);
for(int i = 0; i < n; i++){
if((part[i] & 1) == z){
color[i] = c;
}
}
while(true){
int x = perform_experiment(color);
if(x == N + 1){
break;
}
vector<int>cand;
for(int i = 0; i < n; i++){
if(color[i] == -1 && (cand.empty() || cand.back() != part[i])){
cand.push_back(part[i]);
}
}
int low = 0, high = int(cand.size()) - 2, pos = -1;
while(low <= high){
int mid = (low + high) >> 1;
vector<bool>mark(N, false);
for(int i = 0; i <= mid; i++){
mark[cand[i]] = true;
}
vector<int>ncolor = color;
for(int i = 0; i < n; i++){
if(mark[part[i]]){
ncolor[i] = n;
}
}
if(perform_experiment(ncolor) == x){
low = (pos = mid) + 1;
}
else{
high = mid - 1;
}
}
pos++;
for(int i = 0; i < n; i++){
if(part[i] == cand[pos]){
ans[i] = c;
color[i] = n;
}
}
}
}
}
return ans;
}
}
namespace sub4{
vector<int>solve(){
vector<int>ans(n);
for(int i = 0; i < n; i++){
int low = 0, high = n - 2;
while(low <= high){
int mid = (low + high) >> 1;
vector<int>c(n, n);
c[i] = -1;
for(int j = 0, cur = 0; j < n && cur <= mid; j++){
if(j != i){
c[j] = cur++;
}
}
if(perform_experiment(c) == mid + 2 + int(mid != n - 2)){
low = ans[i] = mid + 1;
}
else{
high = mid - 1;
}
}
}
return ans;
}
}
namespace sub5{
struct DSU{
vector<int>lab;
void init(){
lab.resize(n);
iota(lab.begin(), lab.end(), 0);
}
int find_set(int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
}
bool merge(int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
lab[i] = j;
return true;
}
return false;
}
};
vector<int>solve(){
vector<vector<int>>g(n);
for(int i = 0; i < m; i++){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
DSU d1, d2;
d1.init();
d2.init();
function<bool(int, vector<int>)>is_same = [&] (int i, vector<int>J){
vector<int>c(n, n);
c[i] = -1;
vector<bool>vis(n, false);
vis[i] = true;
for(int& j : J){
c[j] = -1;
vis[j] = true;
}
int cnt = 1 + J.size();
for(int x = 0; x < n; x++){
if(!vis[x]){
queue<int>q;
q.push(x);
cnt++;
while(!q.empty()){
int u = q.front();
q.pop();
for(int& v : g[u]){
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
}
return perform_experiment(c) < cnt;
};
vector<int>h(n, -1);
function<void(int, int)>dfs_1;
dfs_1 = [&] (int s, int p){
vector<pair<int, int>>back_edge;
for(int& d : g[s]){
if(d != p && h[d] != -1){
back_edge.push_back(make_pair(d1.find_set(d), d));
}
}
if(!back_edge.empty()){
sort(back_edge.begin(), back_edge.end());
vector<int>cand(1, back_edge[0].second);
for(int i = 1; i < back_edge.size(); i++){
if(back_edge[i].first != back_edge[i - 1].first){
cand.push_back(back_edge[i].second);
}
}
while(true){
if(!is_same(s, cand)){
break;
}
int low = 0, high = int(cand.size()) - 2, pos = -1;
while(low <= high){
int mid = (low + high) >> 1;
if(!is_same(s, vector<int>(cand.begin(), cand.begin() + mid + 1))){
low = (pos = mid) + 1;
}
else{
high = mid - 1;
}
}
d1.merge(s, cand[pos + 1]);
cand.erase(cand.begin() + pos + 1);
}
}
for(int& d : g[s]){
if(d != p && h[d] == -1){
h[d] = h[s] + 1;
if(is_same(s, {d})){
d1.merge(s, d);
}
dfs_1(d, s);
}
}
};
dfs_1(h[0] = 0, -1);
bool is_unique = true;
for(int i = 1; i < n; i++){
if(d1.find_set(i) != d1.find_set(0)){
is_unique = false;
break;
}
}
if(is_unique){
for(int i = 0; i < n; i++){
vector<int>c(n, -1);
c[0] = i;
if(perform_experiment(c) == 1){
fill(c.begin(), c.end(), i);
return c;
}
}
}
vector<vector<int>>tree(n);
for(int i = 0; i < m; i++){
if(d2.merge(d1.find_set(x[i]), d1.find_set(y[i]))){
tree[d1.find_set(x[i])].push_back(d1.find_set(y[i]));
tree[d1.find_set(y[i])].push_back(d1.find_set(x[i]));
}
}
int root;
for(int i = 0; i < n; i++){
if(d1.find_set(i) == i){
root = i;
break;
}
}
fill(h.begin(), h.end(), -1);
vector<int>ans(n, -1);
function<void(int)>dfs_2;
dfs_2 = [&] (int s){
for(int& d : tree[s]){
if(h[d] == -1){
h[d] = h[s] + 1;
dfs_2(d);
}
}
};
h[root] = 0;
dfs_2(root);
for(int c = 0; c < n; c++){
for(int z = 0; z < 2; z++){
vector<int>color(n, -1);
for(int i = 0; i < n; i++){
if((h[d1.find_set(i)] & 1) == z){
color[i] = c;
}
}
d2.init();
while(true){
int cnt_com = 0;
d2.init();
for(int i = 0; i < m; i++){
if(color[x[i]] == color[y[i]] && color[x[i]] != -1){
d2.merge(d1.find_set(x[i]), d1.find_set(y[i]));
}
}
for(int i = 0; i < n; i++){
if(d1.find_set(i) == i && d2.find_set(i) == i){
cnt_com++;
}
}
if(perform_experiment(color) == cnt_com){
break;
}
vector<int>cand;
vector<bool>mark(n, false);
for(int i = 0; i < n; i++){
if(color[i] == -1 && ans[i] == -1 && !mark[d1.find_set(i)]){
mark[d1.find_set(i)] = true;
cand.push_back(d1.find_set(i));
}
}
int low = 0, high = int(cand.size()) - 2, pos = high + 1;
while(low <= high){
int mid = (low + high) >> 1, expected = 0;
fill(mark.begin(), mark.end(), false);
for(int i = 0; i <= mid; i++){
mark[cand[i]] = true;
}
vector<int>ncolor = color;
for(int i = 0; i < n; i++){
if(mark[d1.find_set(i)]){
ncolor[i] = n;
}
}
d2.init();
for(int i = 0; i < m; i++){
if(ncolor[x[i]] == ncolor[y[i]] && ncolor[x[i]] != -1){
d2.merge(d1.find_set(x[i]), d1.find_set(y[i]));
}
}
for(int i = 0; i < n; i++){
if(d1.find_set(i) == i && d2.find_set(i) == i){
expected++;
}
}
if(perform_experiment(ncolor) == expected){
high = (pos = mid) - 1;
}
else{
low = mid + 1;
}
}
for(int i = 0; i < n; i++){
if(d1.find_set(i) == cand[pos]){
ans[i] = c;
color[i] = n;
}
}
}
}
}
return ans;
}
}
vector<int>find_colours(int __n, vector<int>__x, vector<int>__y) {
swap(x, __x);
swap(y, __y);
m = x.size();
if((n = __n) <= 50){
return sub12::solve();
}
if(sub3::check_subtask()){
return sub3::solve();
}
if(m == ((n * (n - 1)) >> 1)){
return sub4::solve();
}
return sub5::solve();
}
