#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
/****************************************************/
namespace com {
const int MAXN = 10000, BITS = 60;
v<int> adj[MAXN];
v<pii> subt[MAXN];
int key[MAXN];
template <int SZ> struct UnionFind {
int par[SZ];
UnionFind() {
FOR(i, 0, SZ) par[i] = i;
}
int find(int x) {
if (par[x] != x) par[x] = find(par[x]);
return par[x];
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
par[y] = x;
return true;
}
};
void make_tree(int m, int A[], int B[]) {
UnionFind<MAXN> uf;
FOR(i, 0, m) if (uf.unite(A[i], B[i])) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
void getinit(int x, int p, v<pii> &tree) {
if (tree.size() == BITS) return;
tree.push_back({ x,0 });
for (auto c : adj[x]) if (c != p) getinit(c, x, tree);
}
bool isEdge(int a, int b) {
return binary_search(all(adj[a]), b);
}
void dfs(int x, int p) {
if (subt[x].empty()) {
v<pii> &tree = subt[x];
tree = subt[p];
int w = -1;
FOR(i, 0, tree.size()) {
if (tree[i].second == 1 && tree[i].first != p) {
w = tree[i].first;
tree.erase(tree.begin() + i);
break;
}
}
assert(w != -1);
for (auto &i : tree) if (isEdge(w, i.first)) i.second--;
tree.push_back({ x,1 });
for (auto &i : tree) if (i.first == p) i.second++;
key[x] = key[w];
}
for (auto c : adj[x]) if (c != p) dfs(c, x);
}
void setup(int N, int M, int A[], int B[]) {
make_tree(M, A, B);
FOR(i, 0, N) sort(all(adj[i]));
v<pii> itree;
getinit(0, -1, itree);
for (auto &i : itree)
for (auto j : itree)
if (isEdge(i.first, j.first))
i.second++;
int k = 0;
for (auto i : itree) {
subt[i.first] = itree;
key[i.first] = k++;
}
dfs(0, -1);
/* FOR(i, 0, N) {
cout << "Node " << i << ":\nTree: ";
v<int> present;
for (auto x : subt[i]) {
cout << x.first << ", ";
present.push_back(key[x.first]);
}
sort(all(present));
cout << "\nKeys: ";
for (auto x : present)
cout << x << ", ";
cout << "\n";
}*/
}
}
using namespace com;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
setup(N, M, A, B);
// cout << "JOI summary::\n";
FOR(i, 0, N) {
int msg = 0;
if (X&(1LL << key[i])) msg = 1;
MessageBoard(i, msg);
// pf("Node %d : key %d : Val %d\n", i, key[i], msg);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
/****************************************************/
namespace com2 {
const int MAXN = 10000, BITS = 60;
v<int> adj[MAXN];
v<pii> subt[MAXN];
int key[MAXN];
int bits[BITS];
v<int> tour;
v<int> res;
bool valid[MAXN];
void gettour(int x, int p) {
tour.push_back(x);
for (auto c : adj[x]) if (c != p && valid[c]) {
gettour(c, x);
tour.push_back(x);
}
}
template <int SZ> struct UnionFind {
int par[SZ];
UnionFind() {
FOR(i, 0, SZ) par[i] = i;
}
int find(int x) {
if (par[x] != x) par[x] = find(par[x]);
return par[x];
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
par[y] = x;
return true;
}
};
void make_tree(int m, int A[], int B[]) {
UnionFind<MAXN> uf;
FOR(i, 0, m) if (uf.unite(A[i], B[i])) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
void getinit(int x, int p, v<pii> &tree) {
if (tree.size() == BITS) return;
tree.push_back({ x,0 });
for (auto c : adj[x]) if (c != p) getinit(c, x, tree);
}
bool isEdge(int a, int b) {
return binary_search(all(adj[a]), b);
}
void dfs(int x, int p) {
if (subt[x].empty()) {
v<pii> &tree = subt[x];
tree = subt[p];
int w = -1;
FOR(i, 0, tree.size()) {
if (tree[i].second == 1 && tree[i].first != p) {
w = tree[i].first;
tree.erase(tree.begin() + i);
break;
}
}
assert(w != -1);
for (auto &i : tree) if (isEdge(w, i.first)) i.second--;
tree.push_back({ x,1 });
for (auto &i : tree) if (i.first == p) i.second++;
key[x] = key[w];
}
for (auto c : adj[x]) if (c != p) dfs(c, x);
}
void setup(int N, int M, int A[], int B[]) {
make_tree(M, A, B);
FOR(i, 0, N) sort(all(adj[i]));
v<pii> itree;
getinit(0, -1, itree);
for (auto &i : itree)
for (auto j : itree)
if (isEdge(i.first, j.first))
i.second++;
int k = 0;
for (auto i : itree) {
subt[i.first] = itree;
key[i.first] = k++;
}
dfs(0, -1);
/* FOR(i, 0, N) {
cout << "Node " << i << ":\nTree: ";
v<int> present;
for (auto x : subt[i]) {
cout << x.first << ", ";
present.push_back(key[x.first]);
}
sort(all(present));
cout << "\nKeys: ";
for (auto x : present)
cout << x << ", ";
cout << "\n";
}*/
}
}
using namespace com2;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
setup(N, M, A, B);
for (auto i : subt[P]) valid[i.first] = 1;
gettour(P, -1);
res.push_back(V);
FOR(i, 1, tour.size())
res.push_back(Move(tour[i]));
FOR(i, 0, tour.size())
bits[key[tour[i]]] = res[i];
ll ans = 0;
FOR(i, 0, BITS)
ans += (1LL << i)*bits[i];
return ans;
}
