#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e5 + 12, b = 60;
mt19937 rng1(123321);
vector<int> g1[N], G1[N];
int tin1[N], timer1, va[N], pr1[N];
bool vis1[N], ok1[N];
ll x;
void build1(int n) {
set<int> cur;
function<void(int)> dd = [&](int v) {
vis1[v] = 1;
for(int to : g1[v]) {
if(!vis1[to]) {
dd(to);
pr1[to] = v;
G1[v].push_back(to);
}
}
};
function<void(int)> dfs = [&](int v){
vis1[v] = 1;
cur.insert(v);
if((int)cur.size() == b) return;
for(int to : G1[v]) {
if(!vis1[to]) {
dfs(to);
if((int)cur.size() == b) return;
}
}
};
auto find = [&](int bl) {
for(int i : cur) {
if(i == bl) continue;
int col = 0;
for(int to : G1[i]) {
if(ok1[to]) {
col++;
}
}
if(i && ok1[pr1[i]]) col++;
if(col == 1) return i;
}
exit(-1);
};
function<void(int, int)> go = [&](int v, int pr) {
for(int to : G1[v]) {
int del = -1;
if(!ok1[to]) {
del = find(v);
ok1[del] = 0;
ok1[to] = 1;
cur.erase(del);
cur.insert(to);
va[to] = va[del];
}
go(to, v);
if(!ok1[to]) {
ok1[del] = 1;
ok1[to] = 0;
cur.insert(del);
cur.erase(to);
}
}
};
dd(0);
for(int i = 0; i < n; i++) {
vis1[i] = 0;
}
dfs(0);
auto it = (cur.begin());
for(int i = 0; i < b; i++) {
ok1[(*it)] = 1;
va[(*it)] = i;
it++;
}
go(0, -1);
for(int i = 0; i < n; i++) {
MessageBoard(i, ((x >> va[i]) & 1));
}
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
x = X;
for(int i = 0; i < m; i++) {
g1[A[i]].push_back(B[i]);
g1[B[i]].push_back(A[i]);
}
for(int i = 0; i < n; i++) {
sort(g1[i].begin(), g1[i].end());
}
build1(n);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e5 + 12, b = 60;
mt19937 rng(123321);
ll d[N], mxd[N], pr[N], timer, sz[N];
vector<int> g[N], G[N];
int tin[N], bt[N], tout[N], val[N];
bool vis[N], ok[N];
set<int> st[N];
void build(int n) {
set<int> cur;
function<void(int)> dd = [&](int v) {
vis[v] = 1;
for(int to : g[v]) {
if(!vis[to]) {
pr[to] = v;
dd(to);
G[v].push_back(to);
}
}
};
function<void(int)> dfs = [&](int v){
vis[v] = 1;
cur.insert(v);
if((int)cur.size() == b) return;
for(int to : G[v]) {
if(!vis[to]) {
dfs(to);
if((int)cur.size() == b) return;
}
}
};
auto find = [&](int bl) {
for(int i : cur) {
if(i == bl) continue;
int col = 0;
for(int to : G[i]) {
if(ok[to]) {
col++;
}
}
if(i && ok[pr[i]]) col++;
if(col == 1) return i;
}
exit(-1);
};
function<void(int, int)> go = [&](int v, int pr) {
for(int to : G[v]) {
int del = -1;
if(!ok[to]) {
del = find(v);
ok[del] = 0;
ok[to] = 1;
cur.erase(del);
cur.insert(to);
val[to] = val[del];
st[to] = cur;
}
go(to, v);
if(!ok[to]) {
ok[del] = 1;
ok[to] = 0;
cur.insert(del);
cur.erase(to);
}
}
};
dd(0);
for(int i = 0; i < n; i++) {
vis[i] = 0;
}
dfs(0);
auto it = (cur.begin());
for(int i = 0; i < b; i++) {
st[(*it)] = cur;
ok[(*it)] = 1;
val[(*it)] = i;
it++;
}
go(0, -1);
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
memset(pr, -1, sizeof(pr));
for(int i = 0; i < m; i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
for(int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end());
}
build(n);
function<void(int, int, int)> dfs = [&](int v, int pr, int f) {
bt[val[v]] = f;
ok[v] = 0;
for(int to : G[v]) {
if(ok[to] && to != pr) {
dfs(to, v, Move(to));
}
}
if(pr != -1) {
Move(pr);
}
};
for(int i = 0; i < n; i++) {
ok[i] = 0;
if(pr[i] != -1) {
G[i].push_back(pr[i]);
}
}
for(int i = 0; i < n; i++) {
sort(G[i].begin(), G[i].end());
assert(G[i] == g[i]);
}
for(int j : st[P]) {
ok[j] = 1;
}
dfs(P, -1, V);
ll res = 0;
for(int i = 0; i < b; i++) {
if(bt[i]) res += (1ll << i);
}
return res;
}
