#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
vector<int>E[N];
bool was[N];
int par[N];
void DFS(int u){
was[u]=true;
for(auto i:E[u]){
if(!was[i]) {par[i]=u;DFS(i);}
}
}
vector<int>vtx[N];
struct DSU{
int par[N+50];
DSU(){Init();}
void Init(){for(int i=0;i<N;i++) par[i]=i;}
int FS(int u){if(par[u]==u)return u;return par[u]=FS(par[u]);}
void US(int u,int v){u=FS(u),v=FS(v);if(u==v) return;par[u]=v;}
}dsu;
vector<int>E1[N],strana[2];
void DFSsetup(int u,int parent=-1,int depth=0){
strana[depth&1].pb(u);
for(auto i:E1[u]){
if(i==parent) continue;
DFSsetup(i,u,depth+1);
}
}
std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y){
vector<int>res(n,0);
for(int i=0;i<X.size();i++) E[X[i]].pb(Y[i]),E[Y[i]].pb(X[i]);
bool subtask3=true;
for(int i=0;i<X.size();i++) if(abs(X[i]-Y[i])!=1) subtask3=false;
/*if(n==2){
for(int i=0;i<=n;i++){
vector<int>temp;
temp.pb(-1),temp.pb(i);
if(perform_experiment(temp)==1){
res[0]=i;
}
temp.clear();
temp.pb(i),temp.pb(-1);
if(perform_experiment(temp)==1){
res[1]=i;
}
}
return res;
}
if(subtask3){
vector<int>temp(n);
for(int c=0;c<n;c++){
int ct1=0;
for(int i=0;i<n;i++) temp[i]=c;
for(int i=2;i<n-1;i+=2) temp[i]=-1,ct1++;
int num=(1+2*ct1-perform_experiment(temp))>>1;
for(int j=1;j<=num;j++){
int ct=0;for(int i=2;i<n-1;i+=2) ct++;
int l=1,r=ct,ind=0;
while(l<=r){
int mid=l+r>>1;
for(int i=0;i<n;i++) temp[i]=c;
for(int i=2;i<=2*mid;i+=2) temp[i]=-1;
int x=perform_experiment(temp);
int y=2*mid+1-2*j;
if(x<=y){ind=2*mid;r=mid-1;}
else l=mid+1;
}
res[ind]=c;
}
ct1=0;
for(int i=0;i<n;i++) temp[i]=c;
for(int i=1;i<n-1;i+=2) temp[i]=-1,ct1++;
num=(1+2*ct1-perform_experiment(temp))>>1;
for(int j=1;j<=num;j++){
int ct=0;
for(int i=1;i<n-1;i+=2) ct++;
int l=1,r=ct,ind=0;
while(l<=r){
int mid=l+r>>1;
for(int i=0;i<n;i++) temp[i]=c;
for(int i=1;i<=2*mid-1;i+=2) temp[i]=-1;
int x=perform_experiment(temp);
int y=2*mid+1-2*j;
if(x<=y){ind=2*mid-1;r=mid-1;}
else l=mid+1;
}
res[ind]=c;
}
for(int i=1;i<n;i++) temp[i]=c;temp[0]=-1;
if(perform_experiment(temp)==1) res[0]=c;
for(int i=0;i<n-1;i++) temp[i]=c;temp[n-1]=-1;
if(perform_experiment(temp)==1) res[n-1]=c;
}
return res;
}
if(n<=50){
int root=0;
for(int u=1;u<n;u++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) was[j]=false;
DFS(u);
int v=root;
vector<int>temp;for(int j=0;j<n;j++) temp.pb(n);
for(int j=0;j<n;j++) was[j]=false;
while(v!=u){
temp[v]=i;
was[v]=true;
v=par[v];
}
temp[u]=-1;
was[u]=true;
//printf("%i %i: ",root,u);for(auto j:temp) printf("%i ",j);printf("\n");
int x=perform_experiment(temp);
int ct=0;
for(int j=0;j<n;j++) if(!was[j]){ct++;DFS(j);}
//printf("%i %i\n",ct,x);
if(ct+1==x) res[u]=i;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) was[j]=false;
DFS(0);
int v=1;
vector<int>temp;for(int j=0;j<n;j++) temp.pb(n);
for(int j=0;j<n;j++) was[j]=false;
while(v!=0){
temp[v]=i;
was[v]=true;
v=par[v];
}
temp[0]=-1;
was[0]=true;
int x=perform_experiment(temp);
int ct=0;
for(int j=0;j<n;j++) if(!was[j]){ct++;DFS(j);}
if(ct+1==x) res[0]=i;
}
return res;
}
if(2*X.size()==n*(n-1)){
for(int i=0;i<n;i++){
res[i]=n-1;
int l=0,r=n-1;
while(l<=r){
int mid=l+r>>1;
vector<int>temp;for(int j=0;j<n;j++) temp.pb(n);
temp[i]=-1;
for(int j=0,ct=0;ct<=mid;j++){
if(j==i) continue;
temp[j]=ct;
ct++;
}
int ct=0;bool was[n+10]={false};
for(int j=0;j<n;j++){
if(j==i) continue;
if(!was[temp[j]]) ct++;
was[temp[j]]=true;
}
//for(int j=0;j<n;j++) printf("%i ",temp[j]);printf("\n");
int x=perform_experiment(temp);
if(x==ct){
res[i]=mid;
r=mid-1;
}
else l=mid+1;
}
}
return res;
}*/
vector<int>temp(n);
vtx[0].pb(0);
for(int u=1;u<n;u++){
int num=1;
for(int i=0;i<n;i++) temp[i]=n;
for(int i=0;i<u;i++){for(auto j:vtx[i]) temp[j]=-1;if(!vtx[i].empty())num++;}
temp[u]=-1;
num-=perform_experiment(temp);
for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=n) was[i]=true;}
for(int i=0;i<n;i++) if(temp[i]==n&&!was[i])DFS(i),num++;
vtx[u].pb(u);
while(num--){
int l=0,r=u-1,nxt=u;
while(l<=r){
int mid=l+r>>1;
int x=1;
for(int i=0;i<n;i++) temp[i]=n;
for(int i=0;i<=mid;i++){for(auto j:vtx[i]) temp[j]=-1;if(!vtx[i].empty())x++;}
temp[u]=-1;
x-=perform_experiment(temp);
for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=n) was[i]=true;}
for(int i=0;i<n;i++) if(temp[i]==n&&!was[i])DFS(i),x++;
if(x>0){nxt=mid;r=mid-1;}
else l=mid+1;
}
if(nxt==u) continue;
while(!vtx[nxt].empty()) vtx[u].pb(vtx[nxt].back()),vtx[nxt].pop_back();
}
}
res.resize(n);
for(int i=0;i<n;i++) for(auto j:vtx[i]) res[j]=i;
//for(auto i:res) cerr<<i<<" ";cerr<<endl;
for(int i=0;i<X.size();i++){
int u=res[X[i]],v=res[Y[i]];
if(u==v) continue;
if(dsu.FS(u)==dsu.FS(v)) continue;
dsu.US(u,v);
E1[u].pb(v),E1[v].pb(u);
//printf("%i %i - %i %i\n",u,v,X[i],Y[i]);
}
DFSsetup(n-1);
//for(auto i:strana[0]) cerr<<i<<" ";cerr<<endl;
//for(auto i:strana[1]) cerr<<i<<" ";cerr<<endl;
if(strana[1].empty()){
for(int c=0;c<n;c++){
for(int i=0;i<n;i++) temp[i]=c;
temp[0]=-1;
if(perform_experiment(temp)==1){
for(int i=0;i<n;i++) res[i]=c;
break;
}
}
return res;
}
vector<int>res1=res;
for(int c=0;c<n;c++){
for(int bit=0;bit<=1;bit++){
int num=0;
for(int i=0;i<n;i++) temp[i]=c;
for(auto i:strana[bit]){for(auto j:vtx[i]) temp[j]=-1;num++;}
num-=perform_experiment(temp);
for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=c) was[i]=true;}
for(int i=0;i<n;i++)if(temp[i]==c&&!was[i])DFS(i),num++;
//printf("%i %i\n",c,bit);
int poslednji=-1;
vector<int>izbrisi;
while(num){
int l=poslednji+1,r=strana[bit].size()-1,ind=-1;
while(l<=r){
int mid=l+r>>1,x=0;
for(int i=0;i<n;i++) temp[i]=c;
for(int i=poslednji+1;i<=mid;i++){for(auto j:vtx[strana[bit][i]]) temp[j]=-1;x++;}
x-=perform_experiment(temp);
for(int i=0;i<n;i++){was[i]=false;if(temp[i]!=c) was[i]=true;}
for(int i=0;i<n;i++)if(temp[i]==c&&!was[i])DFS(i),x++;
//for(auto i:temp) printf("%i ",i);printf("\n");
//printf(" %i %i\n",perform_experiment(temp),x);
if(x>0){ind=mid;r=mid-1;}
else l=mid+1;
}
if(ind==-1) break;
for(auto i:vtx[strana[bit][ind]]) res[i]=c;
poslednji=ind;
izbrisi.pb(ind);
num-=E1[strana[bit][ind]].size();
//printf(" %i %i\n",ind,strana[bit][ind]);
}
vector<int>nesto;
for(int i=0,j=0;i<strana[bit].size();i++){
if(j<izbrisi.size()&&i==izbrisi[j]){j++;continue;}
nesto.pb(strana[bit][i]);
}
strana[bit]=nesto;
}
}
return res;
}
