#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;
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){
n=N;m=M;
init();
rep(i,0,m-1){
ll u=A[i],v=B[i];
if(findsu(u)!=findsu(v)){
adj[u].push_back(v);
adj[v].push_back(u);
combine(u,v);
}
}
dfs(0,-1);
rep(i,0,n-1) MessageBoard(i,(X>>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;
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){
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) {
n=N;m=M;
init();
rep(i,0,m-1){
ll u=A[i],v=B[i];
if(findsu(u)!=findsu(v)){
adj[u].push_back(v);
adj[v].push_back(u);
combine(u,v);
}
}
par[0]=-1;
dfs(0,-1);
upd(P,V);
while(sz[P]<60&&par[P]!=-1){
upd(par[P],Move(par[P]));
P=par[P];
if(check()) return ans;
}
DFS(P,par[P]);
return ans;
}
