#include<bits/stdc++.h>
#define MAXN 10007
using namespace std;
#include "Joi.h"
namespace Alice{
int n,m;
vector<int> v[MAXN];
const int bits=60;
int bit[MAXN];
bool vis[MAXN];
vector<int> tree[MAXN],special;
vector<int> topsort[MAXN];
int num;
void dfs(int x,int p){
if(num==bits)return;
num++; vis[x]=true;
special.push_back(x);
bit[x]=num-1;
if(p!=0){
tree[p].push_back(x);
tree[x].push_back(p);
}
for(int i:v[x]){
if(i==p)continue;
dfs(i,x);
}
}
void dfs2(int x,int p,int root){
for(int i:tree[x]){
if(i==p)continue;
dfs2(i,x,root);
}
topsort[root].push_back(bit[x]);
}
void dfs3(int x,int p,int pos,int id){
if(!vis[x]){
bit[x]=topsort[id][pos%bits];
}
for(int i:v[x]){
if(i==p or vis[i])continue;
dfs3(i,x,pos+1,id);
}
}
};
void Joi(int N, int M, int A[], int B[], long long X, int T){
using namespace Alice;
n=N; m=M;
for(int i=0;i<m;i++){
A[i]++; B[i]++;
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
A[i]--; B[i]--;
}
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
}
dfs(1,0);
for(int i:special){
dfs2(i,0,i);
}
for(int i:special){
dfs3(i,0,-1,i);
}
for(int i=0;i<n;i++){
MessageBoard(i, ((1LL<<bit[i+1])&X) > 0 );
}
return;
}
#include<bits/stdc++.h>
#define MAXN 10007
using namespace std;
#include "Ioi.h"
namespace Bob{
int n,m,parent[MAXN];
vector<int> v[MAXN];
const int bits=60;
int bit[MAXN];
bool vis[MAXN];
vector<int> tree[MAXN],special;
vector<int> topsort[MAXN];
int num;
int sol[70];
bool used[70];
long long ans;
void dfs(int x,int p){
parent[x]=p;
if(num<bits){
num++; vis[x]=true;
special.push_back(x);
bit[x]=num-1;
if(p!=0){
tree[p].push_back(x);
tree[x].push_back(p);
}
}
for(int i:v[x]){
if(i==p)continue;
dfs(i,x);
}
}
void dfs2(int x,int p,int root){
for(int i:tree[x]){
if(i==p)continue;
dfs2(i,x,root);
}
topsort[root].push_back(bit[x]);
}
void dfs3(int x,int p,int pos,int id){
if(!vis[x]){
bit[x]=topsort[id][pos%bits];
}
for(int i:v[x]){
if(i==p or vis[i])continue;
dfs3(i,x,pos+1,id);
}
}
void dfs4(int x,int curr){
used[bit[x]]=true;
sol[bit[x]]=curr;
for(int i:tree[x]){
if(!used[bit[i]]){
dfs4(i,Move(i-1));
Move(x-1);
}
}
}
};
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
using namespace Bob;
n=N; m=M;
for(int i=0;i<m;i++){
A[i]++; B[i]++;
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
A[i]--; B[i]--;
}
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
}
dfs(1,0);
for(int i:special){
dfs2(i,0,i);
}
for(int i:special){
dfs3(i,0,-1,i);
}
P++; used[bit[P]]=true;
sol[bit[P]]=V;
for(int i=1;i<=bits-1 and !vis[P];i++){
P=parent[P];
V=Move(P-1);
if(vis[P])break;
used[bit[P]]=true;
sol[bit[P]]=V;
}
if(vis[P]){
dfs4(P,V);
}
for(int i=0;i<bits;i++){
ans+=(long long) (1LL<<i) * sol[i];
}
return ans;
}
