#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int BITS = 60;
class DisjointSet {
public:
vector<int> p;
vector<int> sz;
vector<int> hist;
DisjointSet() {}
DisjointSet(int n) : p(n), sz(n, 1) {
iota(begin(p), end(p), 0);
}
void clear() {
for (auto i : hist) {
p[i] = i;
sz[i] = 1;
}
hist.clear();
}
int Unite(int x, int y) {
hist.emplace_back(x);
hist.emplace_back(y);
x = Find(x), y = Find(y);
if (x == y) return 0;
sz[y] += sz[x];
p[x] = y;
return 1;
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
int Size(int x) {
return sz[Find(x)];
}
bool SameSet(int x, int y) {
return Find(x) == Find(y);
}
};
vector<int> ord;
vector<int> vis;
vector<int> parent;
vector<vector<int>> adj;
vector<int> color;
vector<vector<int>> reach;
void Dfs(int u) {
ord.emplace_back(u);
vis[u] = 1;
for (auto v : adj[u]) if (!vis[v]) {
parent[v] = u;
Dfs(v);
}
}
void Init(int N, int M, vector<int> A, vector<int> B) {
adj.resize(N);
vis.assign(N, 0);
parent.assign(N, -1);
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
Dfs(0);
reach.resize(N);
color.assign(N, -1);
DisjointSet D(N);
for (int i = 1; i < BITS; i++) {
D.Unite(parent[ord[i]], ord[i]);
}
for (int i = 0; i < BITS; i++) {
if (i + 1 < BITS) {
assert(D.SameSet(ord[i], ord[i + 1]));
}
color[ord[i]] = i;
for (int j = 0; j < BITS; j++) {
reach[ord[i]].emplace_back(ord[j]);
}
}
D.clear();
for (int i = BITS; i < N; i++) {
int u = ord[i];
int v = parent[u];
static vector<int> marked(N);
for (auto r : reach[v]) marked[r] = 1;
for (auto exclude : reach[v]) if (exclude != v) {
marked[exclude] = 0;
D.Unite(u, v);
for (auto r : reach[v]) if (marked[r]) {
if (parent[r] != -1 && marked[parent[r]]) {
D.Unite(r, parent[r]);
}
}
if (D.Size(u) == BITS) {
vector<int> hascolor(BITS, 0);
reach[u].emplace_back(u);
for (auto r : reach[v]) if (marked[r]) {
reach[u].emplace_back(r);
hascolor[color[r]] = 1;
}
assert(count(begin(hascolor), end(hascolor), 0) == 1);
for (int i = 0; i < BITS; i++) {
if (hascolor[i] == 0) {
color[u] = i;
}
}
}
D.clear();
marked[exclude] = 1;
if (!reach[u].empty()) {
break;
}
}
for (auto r : reach[v]) marked[r] = 0;
}
for (int i = 0; i < N; i++) {
assert(color[i] != -1);
assert(reach[i].size() == BITS);
vector<int> c(BITS);
for (auto j : reach[i]) {
assert(c[color[j]] == 0);
c[color[j]] = 1;
}
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
Init(N, M, vector<int>(A, A + M), vector<int>(B, B + M));
for (int i = 0; i < N; i++) {
MessageBoard(i, !!(X & (1ll << color[i])));
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int BITS = 60;
class DisjointSet {
public:
vector<int> p;
vector<int> sz;
vector<int> hist;
DisjointSet() {}
DisjointSet(int n) : p(n), sz(n, 1) {
iota(begin(p), end(p), 0);
}
void clear() {
for (auto i : hist) {
p[i] = i;
sz[i] = 1;
}
hist.clear();
}
int Unite(int x, int y) {
hist.emplace_back(x);
hist.emplace_back(y);
x = Find(x), y = Find(y);
if (x == y) return 0;
sz[y] += sz[x];
p[x] = y;
return 1;
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
int Size(int x) {
return sz[Find(x)];
}
bool SameSet(int x, int y) {
return Find(x) == Find(y);
}
};
vector<int> ord;
vector<int> vis;
vector<int> parent;
vector<vector<int>> adj;
vector<int> color;
vector<vector<int>> reach;
void Dfs(int u) {
ord.emplace_back(u);
vis[u] = 1;
for (auto v : adj[u]) if (!vis[v]) {
parent[v] = u;
Dfs(v);
}
}
void Init(int N, int M, vector<int> A, vector<int> B) {
adj.resize(N);
vis.assign(N, 0);
parent.assign(N, -1);
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
Dfs(0);
reach.resize(N);
color.assign(N, -1);
DisjointSet D(N);
for (int i = 1; i < BITS; i++) {
D.Unite(parent[ord[i]], ord[i]);
}
for (int i = 0; i < BITS; i++) {
if (i + 1 < BITS) {
assert(D.SameSet(ord[i], ord[i + 1]));
}
color[ord[i]] = i;
for (int j = 0; j < BITS; j++) {
reach[ord[i]].emplace_back(ord[j]);
}
}
D.clear();
for (int i = BITS; i < N; i++) {
int u = ord[i];
int v = parent[u];
static vector<int> marked(N);
for (auto r : reach[v]) marked[r] = 1;
for (auto exclude : reach[v]) if (exclude != v) {
marked[exclude] = 0;
D.Unite(u, v);
for (auto r : reach[v]) if (marked[r]) {
if (parent[r] != -1 && marked[parent[r]]) {
D.Unite(r, parent[r]);
}
}
if (D.Size(u) == BITS) {
vector<int> hascolor(BITS, 0);
reach[u].emplace_back(u);
for (auto r : reach[v]) if (marked[r]) {
reach[u].emplace_back(r);
hascolor[color[r]] = 1;
}
assert(count(begin(hascolor), end(hascolor), 0) == 1);
for (int c = 0; c < BITS; c++) {
if (hascolor[c] == 0) {
color[u] = c;
}
}
}
D.clear();
marked[exclude] = 1;
if (!reach[u].empty()) {
break;
}
}
for (auto r : reach[v]) marked[r] = 0;
}
for (int i = 0; i < N; i++) {
assert(color[i] != -1);
assert(reach[i].size() == BITS);
vector<int> c(BITS);
for (auto j : reach[i]) {
assert(c[color[j]] == 0);
c[color[j]] = 1;
}
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
Init(N, M, vector<int>(A, A + M), vector<int>(B, B + M));
vector<vector<int>> tree(N);
for (int i = 1; i < N; i++) {
tree[parent[i]].emplace_back(i);
tree[i].emplace_back(parent[i]);
}
vector<int> sub(N);
for (auto i : reach[P]) {
sub[i] = 1;
}
vector<int> path;
function<void(int, int)> FindPath = [&](int u, int p) {
assert(sub[u] == 1);
path.emplace_back(u);
for (auto v : tree[u]) if (sub[v] == 1 && v != p) {
FindPath(v, u);
path.emplace_back(u);
}
};
FindPath(P, -1);
assert(path.size() == 2 * BITS - 1);
int u = P, val = V;
long long ans = 0;
for (auto v : path) {
if (u != v) {
tie(u, val) = make_pair(v, Move(v));
}
if (val) {
ans |= 1ll << color[u];
}
}
return ans;
}
