#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
static vector<int> adj2[12269];
static bool vis2[12269];
static int val2[12269];
static int nxt2;
static void dfs2(int node, long long X, int par) {
val2[node] = nxt2;
nxt2 = (nxt2 + 1) % 60;
long long res = (X & (1ll << val2[node]));
if(res > 0) res = 1;
MessageBoard(node, (int) res);
vis2[node] = 1;
for(int x: adj2[node]) {
if(!vis2[x]) {
dfs2(x, X, node);
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(int i=0; i<M; i++) {
adj2[A[i]].push_back(B[i]);
adj2[B[i]].push_back(A[i]);
}
for(int i=0; i<N; i++) {
sort(adj2[i].begin(), adj2[i].end());
}
for(int i=0; i<N; i++) {
vis2[i] = 0;
}
dfs2(0, X, -1);
}
#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e4 + 10;
static vector<int> adj[MAXN];
static bool vis[MAXN];
static int val[MAXN];
static int sz[MAXN];
static int nxt;
static vector<int> et;
static int p[MAXN];
static void dfs(int node, int par) {
val[node] = nxt;
nxt = (nxt+1) % 60;
vis[node] = 1;
sz[node] = 1;
p[node] = par;
et.push_back(node);
for(int x: adj[node]) {
if(!vis[x]) {
dfs(x, node);
et.push_back(node);
sz[node] += sz[x];
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
nxt = 0;
et.clear();
for(int i=0; i<N; i++) {
adj[i].clear();
}
for(int i=0; i<M; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
for(int i=0; i<N; i++) {
sort(adj[i].begin(), adj[i].end());
}
for(int i=0; i<N; i++) {
vis[i] = 0;
}
dfs(0, -1);
long long ans = 0;
int res[60];
for(int i=0; i<60; i++) res[i] = -1;
res[val[P]] = V;
int l[N];
for(int i=0; i<N; i++) l[i] = -1;
for(int i=0; i<et.size(); i++) {
if(l[et[i]] == -1) l[et[i]] = i;
}
int node = P, idx = l[P];
if(sz[node]>=60) {
set<int> st;
st.insert(val[P]);
while(st.size() != 60) {
idx++;
node = et[idx];
res[val[node]] = Move(node);
st.insert(val[node]);
}
}
else {
int optc = 60;
for(int c=10; c<=180; c++) {
set<int>st;
st.insert(val[P]);
int qcnt=0;
int nd=node;
int ii=idx;
for(int i=0; sz[nd]<min(N,c); i++) {
if(p[nd] != -1) {
nd=p[nd];
ii=l[nd];
st.insert(val[nd]);
qcnt++;
}
else break;
}
while(st.size() != 60) {
ii++;
ii %= (int) et.size();
nd = et[ii];
qcnt++;
st.insert(val[nd]);
}
if(qcnt <= 120) optc = c;
}
set<int>st;
st.insert(val[P]);
for(int i=0; sz[node]<min(N,optc); i++) {
if(p[node] != -1) {
node=p[node];
idx=l[node];
res[val[node]]=Move(node);
st.insert(val[node]);
}
else break;
}
while(st.size() != 60) {
idx++;
idx %= (int) et.size();
node = et[idx];
res[val[node]] = Move(node);
st.insert(val[node]);
}
}
for(int i=0; i<60; i++) {
if(res[i]) ans += (1ll << i);
}
return ans;
}
