#include<bits/stdc++.h>
#include"Joi.h"
using namespace std;
#define color MessageBoard
#define app push_back
const int N = 20001;
vector <int> g[N];
int tin[N], ptr = 0;
bool used[N];
void dfs(int u, long long x) {
used[u] = 1;
tin[u] = ptr++;
int b = tin[u] % 60;
color(u, (x >> b) & 1);
for (int v : g[u]) {
if (!used[v]) {
dfs(v, x);
}
}
}
void Joi(int n, int m, int a[], int b[], long long x, int t) {
for (int i = 0; i < m; ++i) {
g[a[i]].app(b[i]);
g[b[i]].app(a[i]);
}
dfs(0, x);
}
#include<bits/stdc++.h>
#include"Ioi.h"
#define move Move
#define app push_back
using namespace std;
const int N = 20001;
vector <int> g[N];
int tin[N], cnt[N], par[N], ptr = 0;
bool used[N];
vector <int> tree[N];
void dfs(int u) {
used[u] = 1; cnt[u] = 1; tin[u] = ptr++;
for (int v : g[u]) {
if (!used[v]) {
dfs(v);
par[v] = u; tree[u].app(v); cnt[u] += cnt[v];
}
}
}
int vis = 0;
bool want[N], mem[N];
int vert[60];
int ans[N];
void dfs1(int u, int p) {
if (vis == 60) return;
++vis;
int b = tin[u] % 60;
want[u] = vert[b] == -1;
bool want0 = want[u];
for (int v : tree[u]) {
dfs1(v, u);
want[u] |= want[v];
}
mem[u] = !want0 && want[u];
}
void dfs2(int u, int p) {
if (tree[u].empty()) return;
for (int v : tree[u]) {
if (want[v]) {
vert[tin[v] % 60] = v;
ans[v] = move(v);
dfs2(v, u);
move(u);
}
}
}
long long Ioi(int n, int m, int a[], int b[], int u, int v, int t) {
for (int i = 0; i < 60; ++i) vert[i] = -1;
for (int i = 0; i < m; ++i) {
g[a[i]].app(b[i]);
g[b[i]].app(a[i]);
}
dfs(0);
ans[u] = v;
vert[tin[u] % 60] = u;
while (cnt[u] < 60) {
u = par[u];
ans[u] = move(u);
vert[tin[u] % 60] = u;
}
dfs1(u, par[u]);
if (want[u]) dfs2(u, par[u]);
long long x = 0;
for (int i = 0; i < 60; ++i) {
x += (1ll << i) * ans[vert[i]];
}
return x;
}
