#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)
const int maxn = 1e4 + 20;
vector<int> g1[maxn] , adj1[maxn] , shit1;
bool visited1[maxn];
int n1 , m1 , h1[maxn];
void plant1(int v)
{
visited1[v] = 1;
shit1.pb(v);
for(auto u : g1[v])
if(!visited1[u])
{
adj1[v].pb(u);
h1[u] = h1[v] + 1;
plant1(u);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
n1 = N , m1 = M;
for(int i = 0; i < m1; i++)
g1[A[i]].pb(B[i]) , g1[B[i]].pb(A[i]);
plant1(0);
int val = *max_element(h1 , h1 + n1) + 1;
if(val < 60)
{
for(int i = 0; i < n1; i++)
{
if(i < 60)
MessageBoard(shit1[i] , bit(X , i));
else
MessageBoard(shit1[i] , bit(X , h1[shit1[i]]));
}
}
else
for(int i = 0; i < n1; i++)
MessageBoard(i , (X >> (h1[i] % 60))&1);
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)
const int maxn = 1e4 + 20;
vector<int> g[maxn] , adj[maxn] , shit;
bool visited[maxn] , have[maxn];
int n , m , h[maxn] , par[maxn] , Pos[maxn];
void plant(int v)
{
visited[v] = 1;
Pos[v] = shit.size();
shit.pb(v);
for(auto u : g[v])
if(!visited[u])
{
adj[v].pb(u);
h[u] = h[v] + 1;
par[u] = v;
plant(u);
}
}
vector<int> go(int v)
{
vector<int> res;
while(v)
res.pb(v) , v = par[v];
res.pb(v);
reverse(res.begin() , res.end());
return res;
}
void getval(int st , ll &V , int v)
{
if(st == v)
return;
auto b = go(v);
int ind = -1;
for(int i = 0; i < h[v] + 1; i++)
if(b[i] == st)
ind = i;
if(ind == -1)
{
assert(st != par[st]);
st = par[st];
V = Move(st);
getval(st , V , v);
}
else
{
assert(st != b[ind + 1]);
st = b[ind + 1];
V = Move(st);
getval(st , V , v);
}
}
ll Ioi(int N, int M, int A[], int B[], int st , int VV, int T)
{
ll V = VV;
n = N , m = M;
for(int i = 0; i < m; i++)
g[A[i]].pb(B[i]) , g[B[i]].pb(A[i]);
plant(0);
int val = *max_element(h , h + n) + 1;
ll res = 0;
if(val < 60)
{
while(Pos[st] >= 60)
{
res |= (V << h[st]) , have[h[st]] = 1;
V = Move(par[st]);
st = par[st];
}
for(int i = Pos[st]; i < 60; i++)
{
if(have[i])
continue;
getval(st , V , shit[i]);
st = shit[i];
res |= (V << i);
have[i] = 1;
}
for(int i = 59; i >= 0; i--)
{
if(have[i])
continue;
have[i] = 1;
getval(st , V , shit[i]);
st = shit[i];
res |= (V << i);
}
}
else
{
if(h[st] + 1 < 60)
{
while(st)
V = Move(par[st]) , st = par[st];
auto tmp = go(max_element(h , h + n) - h);
for(int i = 0; i < 60; i++)
{
if(st != tmp[i])
V = Move(tmp[i]);
st = tmp[i];
res |= (V << i);
}
}
else
{
for(int i = 0; i < 60; i++)
{
res |= (V << (h[st] % 60));
if(st != par[st])
V = Move(par[st]);
st = par[st];
}
}
}
return res;
}
