#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#include "Joi.h"
vector<int>E[20000];
vector<int>vs;
bool used[20000];
void dfs(int v,int p){
used[v]=true;
vs.push_back(v);
for(int u:E[v]){
if(used[u])continue;
dfs(u,v);
vs.push_back(v);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
rep(i,M){
E[A[i]].push_back(B[i]);
E[B[i]].push_back(A[i]);
}
dfs(0,-1);
set<int>se1,se2;
mt19937 mt(123456789);
vector<int>V;
rep(i,60)V.push_back(i);
int MP[60]{};
for(int v:vs){
if(!se1.count(v)){
se2.insert(v);
}
if(se2.size()==60){
int cnt=0;
shuffle(V.begin(),V.end(),mt);
for(int i:se2){
MP[V[cnt]]++;
MessageBoard(i,X>>V[cnt]&1);
cnt++;
}
for(int i:se2){
se1.insert(i);
}
se2.clear();
}
}
shuffle(V.begin(),V.end(),mt);
int cnt=0;
for(int i:se2){
MP[V[cnt]]++;
MessageBoard(i,X>>V[cnt]&1);
cnt++;
}
}
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#include "Ioi.h"
static vector<int>E[20000];
static vector<int>vs;
static int vid[20000];
static bool used[20000];
static void dfs(int v,int p){
used[v]=true;
vid[v]=vs.size();
vs.push_back(v);
for(int u:E[v]){
if(used[u])continue;
dfs(u,v);
vs.push_back(v);
}
}
long long Ioi(int N, int M, int A[], int B[], int Pos, int V, int T) {
rep(i,M){
E[A[i]].push_back(B[i]);
E[B[i]].push_back(A[i]);
}
dfs(0,-1);
set<int>se1,se2;
map<int,int>id;
mt19937 mt(123456789);
vector<int>R;
rep(i,60)R.push_back(i);
for(int v:vs){
if(!se1.count(v)){
se2.insert(v);
}
if(se2.size()==60){
shuffle(R.begin(),R.end(),mt);
int cnt=0;
for(int i:se2){
id[i]=R[cnt];
cnt++;
}
for(int i:se2){
se1.insert(i);
}
se2.clear();
}
}
int cnt=0;
shuffle(R.begin(),R.end(),mt);
for(int i:se2){
id[i]=R[cnt];
cnt++;
}
int x=vid[Pos];
set<int>se;
int r;
for(r=x;r<vs.size();r++){
se.insert(id[vs[r]]);
if(se.size()==60)break;
}
if(r==vs.size())r=vs.size()-1;
int l;
for(l=x;l>=0;l--){
se.insert(id[vs[l]]);
if(se.size()==60)break;
}
if(l==-1)l=0;
ll ans=0;
ans|=ll(V)<<id[Pos];
if(abs(x-l)<abs(x-r)){
//left
for(int i=x-1;i>=l;i--){
ans|=ll(Move(vs[i]))<<id[vs[i]];
}
for(int i=l+1;i<=r;i++){
ans|=ll(Move(vs[i]))<<id[vs[i]];
}
}
else{
//right
for(int i=x+1;i<=r;i++){
ans|=ll(Move(vs[i]))<<id[vs[i]];
}
for(int i=r-1;i>=l;i--){
ans|=ll(Move(vs[i]))<<id[vs[i]];
}
}
return ans;
}
