#include<bits/stdc++.h>
#include "Joi.h"
#define ll long long
using namespace std;
vector<int>g[20005];
int tin[20005],u=0;
bool viz[200005];
void dfs(int nod,ll x)
{
viz[nod]=1;
tin[nod]=u++;
int num=tin[nod]%60;
MessageBoard(nod,(x>>num)&1);
for(auto it:g[nod]){
if (viz[it]==0)
dfs(it,x);
}
}
void Joi(int n,int m,int a[],int b[],ll x,int t)
{
int i;
for(i=0;i<m;i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
dfs(0,x);
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#include "Ioi.h"
vector<int>g[20005];
int tin[20005],cnt[20005],t[20005],u=0,v[60],ans[20005],h[20005];
bool viz[20005],w[20005];
vector<int>tree[20005];
void dfs(int nod)
{
viz[nod]=1;
cnt[nod]=1;
tin[nod]=u++;
for(auto it:g[nod]){
if (viz[it]==0){
dfs(it);
t[it]=nod;
tree[nod].push_back(it);
cnt[nod]+=cnt[it];
}
}
}
int cur;
void dfs2(int nod,int ta)
{
if (cur==60)
return ;
++cur;
int num=tin[nod]%60;
w[nod]=v[num]==-1;
h[nod]=0;
for(auto it:tree[nod]){
dfs2(it,nod);
w[nod]|=w[it];
h[nod]=max(h[nod],h[it]+1);
}
}
void dfs3(int nod,int tat,bool oki)
{
if (tree[nod].empty())
return ;
int maxi=-1;
for(auto it:tree[nod]){
if (w[it]){
if (maxi==-1 || h[maxi]<h[it])
maxi=it;
}
}
if (oki && maxi!=-1){
for(auto it:tree[nod]){
if (w[it] && it!=maxi){
v[tin[it]%60]=it;
ans[it]=Move(it);
dfs3(it,nod,0);
Move(nod);
}
}
v[tin[maxi]%60]=maxi;
ans[maxi]=Move(maxi);
dfs3(maxi,nod,1);
}
else{
for(auto it:tree[nod]){
if (w[it]){
v[tin[it]%60]=it;
ans[it]=Move(it);
dfs3(it,nod,0);
Move(nod);
}
}
}
}
ll Ioi(int n,int m,int a[],int b[],int x,int y,int st)
{
int i;
for(i=0;i<60;i++)
v[i]=-1;
for(i=0;i<m;i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
dfs(0);
ans[x]=y;
v[tin[x]%60]=x;
while(cnt[x]<60){
x=t[x];
ans[x]=Move(x);
v[tin[x]%60]=x;
}
dfs2(x,t[x]);
if (w[x])
dfs3(x,t[x],1);
ll rez=0;
for(i=0;i<60;i++)
rez=rez+(1LL<<i)*ans[v[i]];
return rez;
}
