//#ifndef rtgsp
#include "Joi.h"
//#endif // rtgsp
#include <bits/stdc++.h>
using namespace std;
const int N=10000;
vector<int> adj[N+1];
vector<int> treeadj[N+1];
int h[N+1];
int mx[N+1];
int pa[N+1];
int id[N+1];
void MessageBoard(int attr, int msg);
void dfs(int u)
{
mx[u]=h[u];
for(int v : adj[u])
{
if(h[v]) continue;
h[v]=h[u]+1;
pa[v]=u;
treeadj[u].push_back(v);
// treeadj[v].push_back(u);
dfs(v);
mx[u]=max(mx[u],mx[v]);
}
}
int dem=0;
void traverse(int u, long long X)
{
MessageBoard(u,(X>>dem)&1);
id[u]=dem++;
if(dem==60) return;
for(int v : treeadj[u])
{
traverse(v,X);
if(dem==60) return ;
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
for(int i=0;i<N;++i)
{
adj[i].clear();
treeadj[i].clear();
}
for(int i=0;i<M;++i)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
h[0]=1;
dfs(0);
if(mx[0]>=60)
{
for(int i=0;i<N;++i)
{
int x = (h[i]-1)%60;
MessageBoard(i,(X>>x)&1);
}
}
else
{
for(int i=0;i<N;++i)
{
sort(treeadj[i].begin(), treeadj[i].end(), [](int a, int b)
{
if(mx[a]==mx[b]) return a>b;
return mx[a]>mx[b];
});
}
dem=0;
fill(id,id+N,-1);
traverse(0,X);
for(int i=0;i<N;++i)
{
if(id[i]==-1) MessageBoard(i,0);
}
}
}
//#ifndef rtgsp
#include "Ioi.h"
//#endif // rtgsp
#include <bits/stdc++.h>
using namespace std;
const int N=10000;
vector<int> adi2[N+1];
vector<int> treeadi2[N+1];
int h2[N+1];
int mx2[N+1];
int pa2[N+1];
int id2[N+1];
//void MessageBoard(int attr, int msg);
int Move(int dest);
void dfs2(int u)
{
mx2[u]=h2[u];
for(int v : adi2[u])
{
if(h2[v]) continue;
h2[v]=h2[u]+1;
pa2[v]=u;
treeadi2[u].push_back(v);
// treeadi2[v].push_back(u);
dfs2(v);
mx2[u]=max(mx2[u],mx2[v]);
}
}
int dem22=0;
long long ans[N+1];
long long mxdepth[N+1];
void traverse(int u)
{
//MessageBoard(u,(X>>dem22)&1);
mxdepth[u]=h2[u];
id2[u]=dem22++;
if(dem22==60) return;
for(int v : treeadi2[u])
{
// int x = Move(v);
//ans[dem22]=x;
traverse(v);
mxdepth[u] = max(mxdepth[u],mxdepth[v]);
if(dem22==60) return ;
}
// Move(pa2[u]);
}
void findans(int u)
{
// cout << u << "L\n";
dem22++;
if(dem22==60) return;
for(int v : treeadi2[u])
{
if(mxdepth[v]==1000000) break;
int x = Move(v);
ans[id2[v]]=x;
findans(v);
//mxdepth[u] = max(mxdepth[u],mxdepth[v]);
if(dem22==60) return ;
}
Move(pa2[u]);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
for(int i=0;i<N;++i)
{
adi2[i].clear();
treeadi2[i].clear();
}
for(int i=0;i<M;++i)
{
adi2[A[i]].push_back(B[i]);
adi2[B[i]].push_back(A[i]);
}
h2[0]=1;
dfs2(0);
if(mx2[0]>=60)
{
if(h2[P]>=60)
{
int x = (h2[P]-1)%60;
ans[x]=V;
for(int i=1;i<=59;++i)
{
P=pa2[P];
int x = (h2[P]-1)%60;
ans[x]=Move(P);
}
}
else
{
if(P==0) ans[0]=V;
while(h2[P]!=1)
{
P=pa2[P];
int x = Move(P);
if(P==0) ans[0]=x;
}
for(int i=1;i<60;++i)
{
for(int v : treeadi2[P])
{
if(mx2[v]>=60)
{
int x = Move(v);
ans[i]=x;
P=v;
break;
}
}
}
}
}
else
{
if(P==0) ans[0]=V;
while(h2[P]!=1)
{
P=pa2[P];
int x = Move(P);
if(P==0) ans[0]=x;
}
for(int i=0;i<N;++i)
{
sort(treeadi2[i].begin(), treeadi2[i].end(), [](int a, int b)
{
if(mx2[a]==mx2[b]) return a>b;
return mx2[a]>mx2[b];
});
}
dem22=0;
fill(mxdepth,mxdepth+N,1000000);
traverse(0);
for(int i=0;i<N;++i)
{
sort(treeadi2[i].begin(), treeadi2[i].end(), [](int a, int b)
{
if(mxdepth[a]==mxdepth[b]) return a>b;
return mxdepth[a]<mxdepth[b];
});
}
dem22=0;
findans(0);
}
long long ret=0;
for(long long i=0;i<60;++i)
{
ret+=(ans[i]<<i);
}
return ret;
}
