#include "sphinx.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const ll inf=1e15;
const ll mod2 =998244353;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,en;
ll kk;
ll el = 19;
struct ib
{
int a,b;
};
struct dsuconcu
{
ib dsu[5001];
void reset()
{
for(int i=1; i<=n; i++)
dsu[i]= {1,i};
}
int get(int x)
{
if(x!=dsu[x].b)dsu[x].b=get(dsu[x].b);
return dsu[x].b;
}
bool noi(int x,int y)
{
x=get(x);
y=get(y);
if(x==y)return 0;
if(dsu[x].a<dsu[y].a)swap(x,y);
dsu[x].a+=dsu[y].a;
dsu[y].b=x;
return 1;
}
} ds,ds2;
int ok[5001];
vector<ib> edge;
vector<int> v[5001],ke[5001],dc[5001];
int depth[5001];
int c[5001];
int d[5001];
void dfs(int x)
{
ok[x]=1;
for(auto f:v[x])
{
if(!ok[f])dfs(f),ke[x].pb(f);
else if(ok[f]==1) dc[x].pb(f);
}
ok[x]=2;
}
bool ask(vector<int>d,int x)
{
dem++;
for(int i=1; i<=n; i++)
c[i]=dem;
for(int i=0; i<d.size(); i++)
c[ds.get(d[i])]=dem-1;
ds2.reset();
for(int i=1; i<=n; i++)
c[i]=c[ds.get(i)];
dem2=n;
for(auto x:edge)
{
if(c[x.a]==c[x.b]&&c[x.a]==dem)
{
if(ds2.noi(x.a,x.b))
dem2--;
}
else if(ds.get(x.a)==ds.get(x.b))
{
if(ds2.noi(x.a,x.b))
dem2--;
}
}
vector<int> gc;
for(int i=1; i<=n; i++)
if(c[i]==dem)gc.pb(x);
else gc.pb(-1);
s10=perform_experiment(gc);
s9=dem2-s10;
return s9>0;
}
void dnc(vector<int>v,int x,int a)
{
if(v.size()==a)
{
for(int i=0; i<v.size(); i++)
ds.noi(v[i],x);
return;
}
vector<int> lft,rgt;
int mid=v.size()>>1;
for(int i=0; i<mid; i++)
lft.pb(v[i]);
for(int i=mid; i<v.size(); i++)
rgt.pb(v[i]);
lft.pb(x);
bool hihi=ask(lft,n);
lft.pop_back();
int ss=s9;
if(ss!=a)dnc(rgt,x,a-s9);
if(ss!=0)
dnc(lft,x,ss);
}
void work(int x)
{
vector<int> vc;
for(auto f:dc[x])
vc.pb(ds.get(f));
sort(vc.begin(),vc.end());
vc.erase(unique(vc.begin(),vc.end()),vc.end());
vc.pb(x);
if(ask(vc,n))
{
vc.pop_back();
dnc(vc,x,s9);
}
}
void des(int x)
{
if(dc[x].size()!=0)work(x);
for(auto f:ke[x])
des(f);
}
void dfc(int x)
{
ok[x]=1;
for(auto f:v[x])
{
if(!ok[f])
{
depth[f]=depth[x]+1;
dfc(f);
}
}
}
bool askk(vector<int>d,int x,vector<int>haha)
{
dem++;
for(int i=1; i<=n; i++)
c[i]=dem;
for(int i=0;i<haha.size();i++)
c[ds.get(haha[i])]=dem-1;
for(int i=0; i<d.size(); i++)
c[ds.get(d[i])]=dem-1;
ds2.reset();
for(int i=1; i<=n; i++)
c[i]=c[ds.get(i)];
dem2=n;
for(auto x:edge)
{
if(c[x.a]==c[x.b]&&c[x.a]==dem)
{
if(ds2.noi(x.a,x.b))
dem2--;
}
else if(ds.get(x.a)==ds.get(x.b))
{
if(ds2.noi(x.a,x.b))
dem2--;
}
}
vector<int> gc;
for(int i=1; i<=n; i++)
if(c[i]==dem)gc.pb(x);
else gc.pb(-1);
s10=perform_experiment(gc);
s9=dem2-s10;
return s9>0;
}
void dnb(vector<int> v,int x,int lst,vector<int> lfec)
{
assert(v.size()!=0);
if(v.size()==1)
{
for(int i=0; i<v.size(); i++)
d[v[i]]=x;
return;
}
vector<int> lft,rgt;
int mid=v.size()>>1;
for(int i=0; i<mid; i++)
lft.pb(v[i]);
for(int i=mid; i<v.size(); i++)
rgt.pb(v[i]);
askk(lft,x,lfec);
int ss=s9;
if(ss==0)
{
for(auto g:lft)
lfec.pb(g);
}
if(ss!=lst)
{
if(ss==0)
{
dnb(rgt,x,lst,lfec);
}else{
askk(rgt,x,lfec);
dnb(rgt,x,s9,lfec);
}
}
if(ss!=0)dnb(lft,x,ss,lfec);
}
void go(int x)
{
vector<int>kaka;
for(int i=0; i<2; i++)
{
for(int j=1; j<=n; j++)
if(ds.get(j)==j&&d[j]==-1&&depth[j]%2==i)
kaka.pb(j);
if(kaka.size()!=0)
{
if(ask(kaka,x))
{
dnb(kaka,x,s9,{});
}
}
kaka.clear();
}
}
vector<int> find_colours(int N,vector<int> X,vector<int> Y)
{
n=N;
m=X.size();
ds.reset();
for(int i=0; i<m; i++)
v[X[i]+1].pb(Y[i]+1),
v[Y[i]+1].pb(X[i]+1),
edge.pb({X[i]+1,Y[i]+1});
dfs(1);
des(1);
vector<int> ans;
for(int i=1; i<=n; i++)
v[i].clear(),ok[i]=0,d[i]=-1;
ds2.reset();
bool hihi=0;
for(auto x:edge)
if(ds2.get(ds.get(x.a))!=ds2.get(ds.get(x.b)))
{
hihi=1;
ds2.noi(ds.get(x.a),ds.get(x.b));
v[ds.get(x.a)].pb(ds.get(x.b));
v[ds.get(x.b)].pb(ds.get(x.a));
}
if(!hihi)
{
vector<int> g;
for(int i=0; i<n; i++)
g.pb(-1);
for(int i=0; i<n; i++)
{
g[0]=i;
if(perform_experiment(g)==1)
{
ans.clear();
for(int j=0; j<n; j++)
ans.pb(i);
return ans;
}
}
assert(0);
}
dfc(ds.get(1));
for(int i=0; i<n; i++)
{
go(i);
}
for(int i=0; i<n; i++)
{
ans.pb(d[ds.get(i+1)]);
}
return ans;
}
