#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
namespace GUI{
vector<pair<int, int>> way[10005];
int use[10005];
int done[10005];
int done_cnt;
int id[10005];
bitset<10000> take[10005];
int dist[10005];
queue<pair<int, int>> q;
void init(int pos){
if(done_cnt == 60) return;
if(id[pos]) return;
id[pos] = ++done_cnt;
if(done_cnt == 60) return;
for(pair<int, int> v : way[pos]) if(!id[v.first] && done_cnt < 60) use[v.second] = 1, init(v.first);
return;
}
void dfs(int pos, int from){
if(id[pos]) return;
for(int i=0; i<10000; i++) dist[i] = 1e9;
q.push({0, pos});
while(!q.empty()){
int d = q.front().first, pos = q.front().second;
q.pop();
if(d >= dist[pos]) continue;
dist[pos] = d;
for(pair<int, int> x : way[pos]) if(use[x.second]) q.push({d+1, x.first});
}
int mxdist=0, mxer=0;
for(int i=0; i<10000; i++){
take[pos][i] = take[from][i];
if(take[pos][i]){
if(dist[i] > mxdist){
mxdist = dist[i];
mxer = i;
}
}
}
take[pos][mxer] = 0;
take[pos][pos] = 1;
id[pos] = id[mxer];
for(pair<int, int> v : way[pos]){
if(id[v.first]) continue;
use[v.second] = 1;
dfs(v.first, pos);
}
return;
}
int bit[65];
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(int i=0; i<M; i++) way[A[i]].push_back({B[i], i}), way[B[i]].push_back({A[i], i});
init(0);
for(int i=0; i<N; i++){
if(id[i]){
for(int j=0; j<N; j++) if(id[j]) take[i][j] = 1;
}
}
for(int i=0; i<N; i++){
if(take[0][i]) for(pair<int, int> v : way[i]) use[v.second] = 1, dfs(v.first, i);
}
for(int i=1; i<=60; i++){
if(X&1) bit[i] = 1;
else bit[i] = 0;
X >>= 1;
}
for(int i=0; i<N; i++) if(bit[id[i]] != 0 && bit[id[i]] != 1){ exit(1); }
for(int i=0; i<N; i++) MessageBoard(i, bit[id[i]]);
return;
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T){
GUI::Joi(N, M, A, B, X, T);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> way[10005];
int use[10005];
int done[10005];
int done_cnt;
int id[10005];
bitset<10000> take[10005];
int dist[10005];
void init(int pos){
if(done_cnt == 60) return;
if(id[pos]) return;
id[pos] = ++done_cnt;
if(done_cnt == 60) return;
for(pair<int, int> v : way[pos]) if(!id[v.first] && done_cnt < 60) use[v.second] = 1, init(v.first);
return;
}
queue<pair<int, int>> q;
void dfs(int pos, int from){
if(id[pos]) return;
for(int i=0; i<10000; i++) dist[i] = 1e9;
q.push({0, pos});
while(!q.empty()){
int d = q.front().first, pos = q.front().second;
q.pop();
if(d >= dist[pos]) continue;
dist[pos] = d;
for(pair<int, int> x : way[pos]) if(use[x.second]) q.push({d+1, x.first});
}
int mxdist=0, mxer=-1;
for(int i=0; i<10000; i++){
take[pos][i] = take[from][i];
if(take[pos][i]){
if(dist[i] > mxdist){
mxdist = dist[i];
mxer = i;
}
}
}
if(mxer == -1){ printf("!!!\n"); }
take[pos][mxer] = 0;
take[pos][pos] = 1;
id[pos] = id[mxer];
for(pair<int, int> v : way[pos]){
if(id[v.first]) continue;
use[v.second] = 1;
dfs(v.first, pos);
}
return;
}
int res[65];
int vs[10005];
int gbP;
void get_ans(int pos){
vs[pos] = 1;
//printf("VS %d\n", pos);
for(pair<int, int> v : way[pos]){
//printf("TRY %d\n", v.first);
if((!take[gbP][v.first]) || vs[v.first]) continue;
int x = Move(v.first);
res[id[v.first]] = x;
get_ans(v.first);
Move(pos);
}
return;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
gbP = P;
for(int i=0; i<M; i++) way[A[i]].push_back({B[i], i}), way[B[i]].push_back({A[i], i});
init(0);
for(int i=0; i<N; i++){
if(id[i]){
for(int j=0; j<N; j++) if(id[j]) take[i][j] = 1;
}
}
for(int i=0; i<N; i++){
if(take[0][i]) for(pair<int, int> v : way[i]) use[v.second] = 1, dfs(v.first, i);
}
res[id[P]] = V;
get_ans(P);
long long X = 0;
for(int i=60; i>=1; i--){
X <<= 1;
X += res[i];
}
return X;
}
