#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];
bool used[20000];
int dep[20000];
int height[20000];
vector<int>vs;
int dfs(int v,int d){
used[v]=true;
dep[v]=d;
vs.push_back(v);
for(int u:E[v]){
if(used[u])continue;
height[v]=max(height[v],dfs(u,d+1)+1);
vs.push_back(v);
}
return height[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,0);
if(height[0]<60){
set<int>se1,se2;
for(int v:vs){
if(!se1.count(v)){
se2.insert(v);
}
if(se2.size()==60){
int cnt=0;
for(int i:se2){
MessageBoard(i,X>>cnt&1);
cnt++;
}
for(int i:se2){
se1.insert(i);
}
se2.clear();
}
}
int cnt=0;
for(int i:se2){
MessageBoard(i,X>>cnt&1);
cnt++;
}
return;
}
rep(i,N){
dep[i]%=60;
MessageBoard(i,X>>dep[i]&1);
}
}
#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>G[20000];
static bool used[20000];
static int dep[20000];
static int height[20000];
static int par[20000];
static vector<int>vs;
static int vid[20000];
static int dfs(int v,int p,int d){
used[v]=true;
vid[v]=vs.size();
vs.push_back(v);
par[v]=p;
dep[v]=d;
for(int u:E[v]){
if(used[u])continue;
G[v].push_back(u);
height[v]=max(height[v],dfs(u,v,d+1)+1);
vs.push_back(v);
}
return height[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,0);
if(height[0]<60){
set<int>se1,se2;
map<int,int>id;
for(int v:vs){
if(!se1.count(v)){
se2.insert(v);
}
if(se2.size()==60){
int cnt=0;
for(int i:se2){
id[i]=cnt;
cnt++;
}
for(int i:se2){
se1.insert(i);
}
se2.clear();
}
}
int cnt=0;
for(int i:se2){
id[i]=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;
set<int>Se;
int l2;
for(l2=x;l2>=0;l2--){
Se.insert(id[vs[l2]]);
if(Se.size()==60)break;
}
if(l2==-1)l2=0;
int r2;
for(r2=x;r2<vs.size();r2++){
Se.insert(id[vs[r2]]);
if(Se.size()==60)break;
}
if(r2==vs.size())r2=vs.size()-1;
if(r2-l2+min(r2-x,x-l2)<r-l+min(r-x,x-l)){
swap(l,l2);
swap(r,r2);
}
set<int>SE;
int l3=x,r3=x;
while(1){
if(l3>0){
SE.insert(id[vs[--l3]]);
}
if(r3<vs.size()-1){
SE.insert(id[vs[++r3]]);
}
if(SE.size()==60)break;
}
if(r3-l3+min(r3-x,x-l3)<r-l+min(r-x,x-l)){
swap(l,l3);
swap(r,r3);
}
map<int,vector<int>>MP;
rep(i,vs.size()){
MP[id[vs[i]]].push_back(i);
}
int l4=x,r4=x;
rep(i,60){
int Min=INT_MAX;
int t=-1;
auto it=lower_bound(MP[i].begin(),MP[i].end(),x);
if(it!=MP[i].end()){
Min=*it-x;
t=*it;
}
if(it!=MP[i].begin()){
it--;
if(Min>x-*it){
Min=x-*it;
t=*it;
}
}
assert(Min<=900);
l4=min(l4,*it);
r4=max(r4,*it);
}
if(r4-l4+min(r4-x,x-l4)<r-l+min(r-x,x-l)){
swap(l,l4);
swap(r,r4);
}
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;
}
rep(i,N){
dep[i]%=60;
}
int pos=Pos;
set<int>se{dep[pos]};
ll ans=ll(V)<<dep[pos];
while(1){
if(se.size()==60||pos==0){
break;
}
pos=par[pos];
ans|=ll(Move(pos))<<dep[pos];
se.insert(dep[pos]);
}
while(1){
if(se.size()==60)break;
for(int u:G[pos]){
if(height[u]+1==height[pos]){
pos=u;
ans|=ll(Move(pos))<<dep[pos];
se.insert(dep[pos]);
break;
}
}
}
return ans;
}
