#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
const static int maxn = 1e4 + 5;
static int lab[maxn];
static int nTime = 0;
static int id[maxn];
static long long res = 0;
static long long cal = 0;
static int sub[maxn] , h[maxn];
static long long can[maxn];
static vector<int> adj[maxn];
static vector<int> child[maxn];
fill_n(lab,maxn,-1);
function<int(int)> FindLab = [&](int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
};
for(int i = 0 ; i < M ; ++i){
int s = FindLab(A[i]);
int d = FindLab(B[i]);
if(s != d){
if(lab[s] > lab[d])swap(s , d);
lab[s] += lab[d];
lab[d] = s;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
function<void(int,int)> DFS = [&](int u , int par){
sub[u] = 1;
for(int c : adj[u]){
if(c != par){
child[u].push_back(c);
h[c] = h[u] + 1;
DFS(c , u);
sub[u] += sub[c];
}
}
};
function<void(int,int)> DFS3 = [&](int u , int par){
id[u] = nTime;
can[u] = (1ll << nTime);
nTime = (nTime + 1) % 60;
if(child[u].empty())return;
stable_sort(child[u].begin(),child[u].end(),[&](const int x , const int y){
return h[x] > h[y];
});
for(int c : child[u]){
if(c != par){
DFS3(c , u);
can[u] |= can[c];
}
}
};
DFS(N / 2 , -1);
DFS3(N / 2 , -1);
for(int i = 0 ; i < N ; ++i){
MessageBoard(i , (X >> id[i]) & 1);
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
const static int maxn = 1e4 + 5;
static int lab[maxn];
static int nTime = 0;
static int id[maxn];
static long long res = 0;
static long long cal = 0;
static int sub[maxn] , h[maxn];
static long long can[maxn];
static int p[maxn];
static vector<int> adj[maxn];
static vector<int> child[maxn];
fill_n(lab,maxn,-1);
function<int(int)> FindLab = [&](int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
};
for(int i = 0 ; i < M ; ++i){
int s = FindLab(A[i]);
int d = FindLab(B[i]);
if(s != d){
lab[s] += lab[d];
lab[d] = s;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
function<void(int,int)> DFS = [&](int u , int par){
sub[u] = 1;
for(int c : adj[u]){
if(c != par){
child[u].push_back(c);
h[c] = h[u] + 1;
DFS(c , u);
sub[u] += sub[c];
}
}
};
function<void(int,int)> DFS3 = [&](int u , int par){
id[u] = nTime;
can[u] = (1ll << nTime);
nTime = (nTime + 1) % 60;
if(child[u].empty())return;
stable_sort(child[u].begin(),child[u].end(),[&](const int x , const int y){
return h[x] > h[y];
});
for(int c : child[u]){
p[c] = u;
DFS3(c , u);
can[u] |= can[c];
}
};
DFS(N / 2 , -1);
DFS3(N / 2 , -1);
function<void(int)> DFS2 = [&](int u){
cal |= (1ll << id[u]);
if(V)res |= (1ll << id[u]);
for(int c : child[u]){
if(__builtin_popcountll(cal) == 60)return;
if((~cal) & can[c]){
V = Move(c);
DFS2(c);
V = Move(u);
}
}
};
function<void(int)> DFS1 = [&](int u){
cal |= (1ll << id[u]);
if(V)res |= (1ll << id[u]);
if(child[u].empty())return;
int first = -1;
for(int i = 0 ; i < (int)child[u].size() ; ++i){
if(__builtin_popcountll(cal) == 60)return;
int c = child[u][i];
if((~cal) & can[c]){
if(first != -1){
V = Move(c);
DFS2(c);
V = Move(u);
}
else{
first = c;
}
}
}
if((~cal) & can[first]){
V = Move(first);
DFS1(first);
}
};
while(sub[P] < 60){
cal |= (1ll << id[P]);
if(V)res |= (1ll << id[P]);
V = Move(p[P]);
P = p[P];
}
DFS1(P);
return res;
}
