#include "Joi.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MX=1e4+5,inf=1e18;
namespace J{
ll n,m,dsu[MX],dfn[MX],timer,sz[MX],ans;
vector<vector<ll> > adj(MX);
void init(){
iota(dsu,dsu+n,0);
}
ll findsu(ll x){
if(dsu[x]==x) return x;
return dsu[x]=findsu(dsu[x]);
}
void combine(ll a,ll b){
a=findsu(a);
b=findsu(b);
if(a==b) return ;
dsu[b]=a;
}
void dfs(ll v,ll lst){
dfn[v]=timer++;
timer%=60;
sz[v]=1;
for(ll cur:adj[v]){
if(cur==lst) continue;
dfs(cur,v);
sz[v]+=sz[cur];
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T){
J::n=N;J::m=M;
J::init();
rep(i,0,J::m-1){
ll u=A[i],v=B[i];
if(J::findsu(u)!=J::findsu(v)){
J::adj[u].push_back(v);
J::adj[v].push_back(u);
J::combine(u,v);
}
}
J::dfs(0,-1);
rep(i,0,J::n-1) MessageBoard(i,(X>>J::dfn[i])&1LL);
}
#include "Ioi.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
namespace I{
const ll MX=1e4+5,inf=1e18;
ll n,m,dsu[MX],dfn[MX],timer,sz[MX],ans,par[MX];
vector<vector<ll> > adj(MX);
bitset<70> flag;
void init(){
iota(dsu+1,dsu+n+1,1);
}
ll findsu(ll x){
if(dsu[x]==x) return x;
return dsu[x]=findsu(dsu[x]);
}
void combine(ll a,ll b){
a=findsu(a);
b=findsu(b);
if(a==b) return ;
dsu[b]=a;
}
void dfs(ll v,ll lst){
dfn[v]=timer++;
timer%=60;
sz[v]=1;
for(ll cur:adj[v]){
if(cur==lst) continue;
par[cur]=v;
dfs(cur,v);
sz[v]+=sz[cur];
}
}
bool check(){
rep(i,0,59) if(!flag[i]) return false;
return true;
}
void upd(ll v,ll x){
//cout<<v<<' '<<x<<' '<<dfn[v]<<'\n';
flag[dfn[v]]=1;
if(x) ans|=(1LL<<dfn[v]);
}
void DFS(ll v,ll lst){
if(check()) return ;
for(ll cur:adj[v]){
if(cur==lst) continue;
upd(cur,Move(cur));
DFS(cur,v);
if(check()) return ;
upd(v,Move(v));
if(check()) return ;
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
I::n=N;I::m=M;
I::init();
rep(i,0,I::m-1){
ll u=A[i],v=B[i];
if(I::findsu(u)!=I::findsu(v)){
I::adj[u].push_back(v);
I::adj[v].push_back(u);
I::combine(u,v);
}
}
I::par[0]=-1;
I::dfs(0,-1);
I::upd(P,V);
while(I::sz[P]<60&&I::par[P]!=-1){
I::upd(I::par[P],Move(I::par[P]));
P=I::par[P];
if(I::check()) return I::ans;
}
I::DFS(P,I::par[P]);
//cout<<I::ans<<'\n';
return I::ans;
}
