#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=10050;
int n,m;
vector<int> E[N];
struct DSU
{
int p[N];
DSU(){}
int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
bool Same(int x, int y){ return Find(x)==Find(y);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);DS.Union(u,v);}
int bt[60],cnt,idx[N][60],csz[N],my[N],sgn[N],up[N];
int Groups(int u, int p, int sz=-1, int cmp=-1)
{
if(sz==-1) sz=60,cmp=cnt++;
sgn[u]=csz[cmp];
idx[cmp][csz[cmp]++]=u;
my[u]=cmp;
sz--;
for(int v:E[u]) if(v!=p)
{
if(sz>0) sz=Groups(v,u,sz,cmp);
else if(Groups(v,u)>0) up[my[v]]=u;
}
return sz;
}
int was[N];
vector<int> Take(int u, int sz, int mark)
{
queue<int> q;
q.push(u);
was[u]=mark;
vector<int> ans;
while(sz--)
{
int x=q.front();
q.pop();
ans.pb(x);
for(int y:E[x]) if(was[y]!=mark && my[y]==my[u])
{
was[y]=mark;
q.push(y);
}
}
return ans;
}
void Joi(int _n, int _m, int A[], int B[], ll X, int T)
{
n=_n;m=_m;
for(int i=0;i<m;i++) if(!DS.Same(A[i]+1,B[i]+1)) AddEdge(A[i]+1,B[i]+1);
for(int i=0;i<60;i++) bt[i]=X>>i&1;
Groups(1,0);
int mark=0;
for(int i=0;i<cnt;i++)
{
if(csz[i]<60)
{
vector<int> tmp=Take(up[i],60-csz[i],++mark);
vector<bool> ban(60,0);
for(int j:tmp) ban[sgn[j]]=1;
for(int j=0,ptr=0;j<csz[i];j++)
{
while(ban[ptr]) ptr++;
sgn[idx[i][j]]=ptr;
ban[ptr]=1;
}
}
}
for(int i=1;i<=n;i++) MessageBoard(i-1,bt[sgn[i]]);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=10050;
int n,m;
vector<int> E[N];
struct DSU
{
int p[N];
DSU(){}
int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
bool Same(int x, int y){ return Find(x)==Find(y);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);DS.Union(u,v);}
int bt[60],cnt,idx[N][60],csz[N],my[N],sgn[N],up[N];
int Groups(int u, int p, int sz=-1, int cmp=-1)
{
if(sz==-1) sz=60,cmp=cnt++;
sgn[u]=csz[cmp];
idx[cmp][csz[cmp]++]=u;
my[u]=cmp;
sz--;
for(int v:E[u]) if(v!=p)
{
if(sz>0) sz=Groups(v,u,sz,cmp);
else if(Groups(v,u)>0) up[my[v]]=u;
}
return sz;
}
int was[N];
vector<int> Take(int u, int sz, int mark)
{
queue<int> q;
q.push(u);
was[u]=mark;
vector<int> ans;
while(sz--)
{
int x=q.front();
q.pop();
ans.pb(x);
for(int y:E[x]) if(was[y]!=mark && my[y]==my[u])
{
was[y]=mark;
q.push(y);
}
}
return ans;
}
bool use[N];
void Walk(int u, int p, bool Ask)
{
if(Ask) bt[sgn[u]]=Move(u-1);
for(int v:E[u]) if(v!=p && use[v])
{
Walk(v,u,1);
Move(u-1);
}
}
ll Ioi(int _n, int _m, int A[], int B[], int P, int V, int T)
{
n=_n;m=_m;
for(int i=0;i<m;i++) if(!DS.Same(A[i]+1,B[i]+1)) AddEdge(A[i]+1,B[i]+1);
Groups(1,0);
int mark=0;
for(int i=0;i<cnt;i++)
{
if(csz[i]<60)
{
vector<int> tmp=Take(up[i],60-csz[i],++mark);
vector<bool> ban(60,0);
for(int j:tmp) ban[sgn[j]]=1;
for(int j=0,ptr=0;j<csz[i];j++)
{
while(ban[ptr]) ptr++;
sgn[idx[i][j]]=ptr;
ban[ptr]=1;
}
}
}
bt[sgn[P+1]]=V;
vector<int> nodes;
if(csz[my[P+1]]<60)
{
nodes=Take(up[my[P+1]],60-csz[my[P+1]],++mark);
}
for(int i=0;i<csz[my[P+1]];i++) nodes.pb(idx[my[P+1]][i]);
for(int u:nodes) use[u]=1;
Walk(P+1,0,0);
ll X=0;
for(int i=0;i<60;i++) X+=(ll)bt[i]<<i;
return X;
}
