#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
using ll = long long;
namespace {
const int N = 1 << 14, B = 60;
int nxt[N];
int head(int u) { return nxt[u] != u ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return 0;
nxt[u] = v; return 1;
}
vector<int> g[N];
int timer = 0; ll x;
void dfs(int u, int p) {
MessageBoard(u, x >> timer & 1);
if (++timer == B) timer = 0;
for (int v : g[u]) if (v != p) dfs(v, u);
}
}
void Joi(int n, int m, int a[], int b[], ll X, int t) {
rep(u, 0, n) nxt[u] = u;
rep(e, 0, m) {
if (unite(a[e], b[e])) {
g[a[e]].push_back(b[e]);
g[b[e]].push_back(a[e]);
}
}
x = X; dfs(0, -1);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
using ll = long long;
namespace {
const int N = 1 << 14, B = 60;
int nxt[N];
int head(int u) { return nxt[u] != u ? nxt[u] = head(nxt[u]) : u; }
bool unite(int u, int v) {
u = head(u); v = head(v);
if (u == v) return 0;
nxt[u] = v; return 1;
}
vector<int> g[N];
int p[N], in[N], out[N], timer = 0;
void init(int u) {
in[u] = timer++;
for (int v : g[u]) {
g[v].erase(find(all(g[v]), u));
p[v] = u; init(v);
}
out[u] = timer;
}
ll cur = 0, x = 0;
bool add(int u, ll z) {
int s = in[u] % B;
cur |= 1ll << s;
x |= z << s;
return __builtin_popcountll(cur) == B;
}
bool dfs(int u, int z) {
if (add(u, z)) return true;
for (int v : g[u]) {
if (dfs(v, Move(v))) return true;
Move(u);
}
return false;
}
}
ll Ioi(int n, int m, int a[], int b[], int P, int V, int T) {
rep(u, 0, n) nxt[u] = u;
rep(e, 0, m) {
if (unite(a[e], b[e])) {
g[a[e]].push_back(b[e]);
g[b[e]].push_back(a[e]);
}
}
init(0);
int right = out[P];
while (right - in[P] < B)
V = Move(p[P]), P = p[P];
assert(dfs(P, V));
return x;
}
