#include "Joi.h"
#include <vector>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
const int bits = 60;
struct edge {
int a, b;
edge() : a(-1), b(-1) {};
edge(int a_, int b_) : a(a_), b(b_) {};
};
pair<vector<vector<edge> >, vector<int> > generate(int N, vector<vector<int> > G) {
vector<int> d(N, -1), par(N, -1);
function<void(int, int)> find_depth = [&](int pos, int pre) {
d[pos] = (pre == -1 ? 0 : d[pre] + 1);
par[pos] = pre;
for(int i : G[pos]) {
if(i != pre) find_depth(i, pos);
}
};
find_depth(0, -1);
vector<int> ord(N);
for(int i = 0; i < N; ++i) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int i, int j) { return d[i] < d[j]; });
vector<int> inv(N);
for(int i = 0; i < N; ++i) inv[ord[i]] = i;
vector<edge> ini;
for(int i = 0; i < bits; ++i) {
for(int j : G[ord[i]]) {
if(inv[j] < bits && ord[i] < j) {
ini.push_back(edge(ord[i], j));
}
}
}
vector<vector<edge> > ans(N);
vector<int> id(N, -1);
for(int i = 0; i < bits; ++i) {
ans[ord[i]] = ini;
id[ord[i]] = i;
}
for(int i = bits; i < N; ++i) {
unordered_map<int, int> tbl;
for(edge j : ans[par[ord[i]]]) {
++tbl[j.a];
++tbl[j.b];
}
int eraser = -1;
for(pair<int, int> j : tbl) {
if(j.second == 1 && j.first != par[ord[i]]) {
eraser = j.first;
}
}
for(edge j : ans[par[ord[i]]]) {
if(j.a != eraser && j.b != eraser) {
ans[ord[i]].push_back(j);
}
}
ans[ord[i]].push_back(edge(ord[i], par[ord[i]]));
id[ord[i]] = id[eraser];
}
return make_pair(ans, id);
}
vector<vector<int> > get_spanning_tree(int N, vector<vector<int> > G) {
vector<vector<int> > ans(N);
vector<bool> vis(N);
function<void(int)> dfs = [&](int pos) {
vis[pos] = true;
for(int i : G[pos]) {
if(!vis[i]) {
ans[pos].push_back(i);
ans[i].push_back(pos);
dfs(i);
}
}
};
dfs(0);
return ans;
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
vector<vector<int> > G(N);
for(int i = 0; i < M; ++i) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
G = get_spanning_tree(N, G);
pair<vector<vector<edge> >, vector<int> > res = generate(N, G);
for(int i = 0; i < N; ++i) {
int val = (X >> res.second[i]) & 1;
MessageBoard(i, val);
}
}
#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
const int bits = 60;
struct edge {
int a, b;
edge() : a(-1), b(-1) {};
edge(int a_, int b_) : a(a_), b(b_) {};
};
pair<vector<vector<edge> >, vector<int> > generate2(int N, vector<vector<int> > G) {
vector<int> d(N, -1), par(N, -1);
function<void(int, int)> find_depth = [&](int pos, int pre) {
d[pos] = (pre == -1 ? 0 : d[pre] + 1);
par[pos] = pre;
for(int i : G[pos]) {
if(i != pre) find_depth(i, pos);
}
};
find_depth(0, -1);
vector<int> ord(N);
for(int i = 0; i < N; ++i) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int i, int j) { return d[i] < d[j]; });
vector<int> inv(N);
for(int i = 0; i < N; ++i) inv[ord[i]] = i;
vector<edge> ini;
for(int i = 0; i < bits; ++i) {
for(int j : G[ord[i]]) {
if(inv[j] < bits && ord[i] < j) {
ini.push_back(edge(ord[i], j));
}
}
}
vector<vector<edge> > ans(N);
vector<int> id(N, -1);
for(int i = 0; i < bits; ++i) {
ans[ord[i]] = ini;
id[ord[i]] = i;
}
for(int i = bits; i < N; ++i) {
unordered_map<int, int> tbl;
for(edge j : ans[par[ord[i]]]) {
++tbl[j.a];
++tbl[j.b];
}
int eraser = -1;
for(pair<int, int> j : tbl) {
if(j.second == 1 && j.first != par[ord[i]]) {
eraser = j.first;
}
}
for(edge j : ans[par[ord[i]]]) {
if(j.a != eraser && j.b != eraser) {
ans[ord[i]].push_back(j);
}
}
ans[ord[i]].push_back(edge(ord[i], par[ord[i]]));
id[ord[i]] = id[eraser];
}
return make_pair(ans, id);
}
vector<vector<int> > get_spanning_tree2(int N, vector<vector<int> > G) {
vector<vector<int> > ans(N);
vector<bool> vis(N);
function<void(int)> dfs = [&](int pos) {
vis[pos] = true;
for(int i : G[pos]) {
if(!vis[i]) {
ans[pos].push_back(i);
ans[i].push_back(pos);
dfs(i);
}
}
};
dfs(0);
return ans;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
vector<vector<int> > G(N);
for(int i = 0; i < M; ++i) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
G = get_spanning_tree2(N, G);
pair<vector<vector<edge> >, vector<int> > res = generate2(N, G);
vector<int> id = res.second;
vector<edge> subgraph = res.first[P];
vector<bool> vis(N);
vector<int> route;
function<void(int)> dfs = [&](int pos) {
vis[pos] = true;
route.push_back(pos);
for(edge e : subgraph) {
if(e.a == pos && !vis[e.b]) dfs(e.b);
if(e.b == pos && !vis[e.a]) dfs(e.a);
route.push_back(pos);
}
};
dfs(P);
route.erase(unique(route.begin(), route.end()), route.end());
long long ans = (long long)(V) << id[P];
for(int i = 1; i < route.size(); ++i) {
ans |= (long long)(Move(route[i])) << id[route[i]];
}
return ans;
}
