#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
static const int MAX_N = 1e4;
static const int K = 60;
static int x[K];
static bool vis[MAX_N];
static vector<int> order;
static vector<int> adj[MAX_N];
void dfs(int u, int a){
MessageBoard(u, x[order.size()%K]);
//cout<<u<<endl;
order.push_back(u);
vis[u] = true;
for(auto v: adj[u]){
if(!vis[v]){
dfs(v, u);
}
}
//cout<<u<<endl;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(long long i = 0; i<K; i++){
if((X&(1LL<<i))>0LL){
x[i] = 1;
}
else{
x[i] = 0;
}
//cout<<x[i]<<" ";
}
for(int i = 0; i<M; i++){
int a, b;
a = A[i];
b =B[i];
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, -1);
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4;
const int K = 60;
static int x2[K], mod[MAX_N], anc[MAX_N], sz[MAX_N], place[MAX_N], among_peers[MAX_N];
static bool vis2[MAX_N], found[K];
static int nb_vis =0;
static vector<int> order2;
static vector<int> adj2[MAX_N];
static vector<int> ch[MAX_N];
void dfs2(int u, int a){
vis2[u] = true;
anc[u] =a;
mod[u] = nb_vis;
place[u] = order2.size();
nb_vis++;
////cout<<u<<" "<<mod[u]<<endl;
order2.push_back(u);
sz[u] =1;
for(auto v: adj2[u]){
if(!vis2[v]){
among_peers[v] = ch[u].size();
ch[u].push_back(v);
dfs2(v, u);
sz[u] += sz[v];
order2.push_back(u);
}
}
}
int nb_found = 0;
void find(int id, int v){
if(!found[id]){
found[id] = true;
nb_found++;
x2[id] = v;
}
}
void explore_after(int u, int order){
//cout<<"exploring "<<u<<" after "<<order<<endl;
//cout<<mod[u]<<endl;
for(int i = order; i<ch[u].size() && nb_found<K; i++){
int next = ch[u][i];
int val = Move(next);
find(mod[next]%K, val);
explore_after(next, 0);
if(nb_found<K){
Move(u);
}
}
//cout<<"done "<<u<<endl;
}
void explore_before(int u, int order){
//cout<<"exploring "<<u<<" before "<<order<<endl;
//cout<<mod[u]<<endl;
for(int i = order; i>=0 && nb_found<K; i--){
int next = ch[u][i];
int val = Move(next);
find(mod[next]%K, val);
explore_before(next, ch[next].size()-1);
if(nb_found<K){
Move(u);
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i = 0; i<M; i++){
int a, b;
a = A[i];
b =B[i];
adj2[a].push_back(b);
adj2[b].push_back(a);
}
dfs2(0, -1);
int cur = P;
find(mod[cur]%K, V);
for(int i= 0; i< order2.size(); i++){
////cout<<i<<" "<<order2[i]<<" | ";
}
////cout<<endl;
explore_after(cur, 0);
//explore_before(cur, ch[cur].size()-1);
while(nb_found<K){
////cout<<anc[cur]<<endl;
int val =Move(anc[cur]);
find(mod[anc[cur]]%K, val);
explore_after(anc[cur], among_peers[cur]+1);
explore_before(anc[cur], among_peers[cur]-1);
//explore_before(anc[cur], among_peers[cur]-1);
cur = anc[cur];
}
/*////cout<<"done going up "<<cur<<" "<<endl;
int pos = place[cur]+1;
////cout<<"first at "<<pos<<endl;
for(int i = pos; nb_found<K; i++){
////cout<<"going to "<<order2[i]<<endl;
int val =Move(order2[i]);
cur= order2[i];
find(mod[cur]%K, val);
}*/
long long res= 0;
for(long long i = 0; i<K; i++){
if(x2[i]){
res+=(1LL<<i);
}
}
////cout<<res<<endl;
return res;
}
