#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//MessageBoard(index,val)
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
static vector<int>adj2[10005];
static int in2[10005];
static int ptr2=-1;
static vector<int>storage2[65];
void dfs3(int index, int par){
in2[index]=++ptr2;
storage2[in2[index]%60].push_back(index);
for(auto it:adj2[index]){
if(it==par) continue;
dfs3(it,index);
}
}
void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long val, int32_t t){
DSU dsu;
dsu.init(n+5);
for(int x=0;x<m;x++){
if(dsu.unite(a[x],b[x])){
adj2[a[x]].push_back(b[x]);
adj2[b[x]].push_back(a[x]);
}
}
dfs3(0,-1);
for(int x=0;x<60;x++){
if(val&(1LL<<x)){
for(auto it:storage2[x]){
MessageBoard(it,1);
}
}
else{
for(auto it:storage2[x]){
MessageBoard(it,0);
}
}
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//MessageBoard(index,val)
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
static vector<int>adj[10005];
static int in[10005];
static int ptr=-1;
static int pp[10005];
void dfs(int index, int par){
in[index]=++ptr;
for(auto it:adj[index]){
if(it==par) continue;
dfs(it,index);
pp[it]=index;
}
}
static int ans[60];
//static int cnt=0;
static vector<int>storage;
void f(int index){
storage.push_back(index);
//if(cnt>=180) return;
////cout << index << " index" << endl;
//cnt++;
//int hold=Move(index);
//ans[in[index]%60]=hold;
}
static bool visited[10005];
void dfs2(int index, int par){
//if(par!=-1) f(index);
//cout << index << " add\n";
visited[index]=true;
for(auto it:adj[index]){
if(it==pp[index]) continue;
if(it==par) continue;
if(visited[it]) continue;
//cout << index << " " << it << " hm" << endl;
//cout << index << " " << it << " nxt" << endl;
f(it);
dfs2(it,index);
}
//cout << index << " " << pp[index] << endl;
//cout << index << " done\n";
if(pp[index]==-1) return;
else if(par==-1){
f(pp[index]);
dfs2(pp[index],-1);
}
else f(par);
}
long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t){
DSU dsu;
dsu.init(n+5);
for(int x=0;x<m;x++){
if(dsu.unite(a[x],b[x])){
adj[a[x]].push_back(b[x]);
adj[b[x]].push_back(a[x]);
//cout << a[x] << " " << b[x] << " edge\n";
}
}
memset(pp,-1,sizeof(pp));
dfs(0,-1);
memset(ans,-1,sizeof(ans));
ans[in[p]%60]=v;
dfs2(p,-1);
long long take=0;
for(int x=0;x<min((int)200,(int)storage.size());x++){
int hold=Move(storage[x]);
ans[in[storage[x]]%60]=hold;
}
for(int x=0;x<60;x++){
//if(ans[x]==-1) ans[x]=0;
take+=(1LL<<x)*ans[x];
//cout << take << endl;
//cout << x << " " << ans[x] << endl;
}
//cout << take << " take" << endl;
return take;
}
