#include "Joi.h"
#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
namespace joi {
const int MAX_BIT = 60;
int n;
vector<vector<int>> e, adj;
vector<bool> vis;
void dfs(int u) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) {
e[u].push_back(v);
e[v].push_back(u);
dfs(v);
}
}
}
int cnt = 0;
set<int> s;
vector<set<int>> f;
vector<int> val(n);
void find(int u, int p) {
val[u] = cnt++;
if (cnt == MAX_BIT) {
return;
}
for (int v : e[u]) {
if (v != p) {
f[u].insert(v);
f[v].insert(u);
find(v, u);
if (cnt == MAX_BIT)
return;
}
}
}
void mark(int u, int p) {
bool in = false, op1 = false, op2 = false;
int x = -1, to = -1;
if (val[u] == -1) {
in = true;
auto t = s.begin();
if (*t == p) t++;
x = *t;
to = *f[x].begin();
s.erase(x);
f[x].erase(to);
f[to].erase(x);
if (f[to].size() == 1) {
op1 = true;
s.insert(to);
}
if (f[p].size() == 1) {
op2 = true;
s.erase(p);
}
f[p].insert(u);
f[u].insert(p);
s.insert(u);
val[u] = val[x];
}
for (int v : e[u]) {
if (v != p) {
mark(v, u);
}
}
if (in) {
s.erase(u);
f[p].erase(u);
f[u].erase(p);
if (op2) {
s.insert(p);
}
if (op1) {
s.erase(to);
}
f[x].insert(to);
f[to].insert(x);
s.insert(x);
}
}
};
using namespace joi;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n = N;
adj.resize(n);
e.resize(n);
for (int i = 0; i < M; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vis.assign(n, 0);
dfs(0);
f.resize(n);
val.resize(n, -1);
find(0, -1);
for (int i = 0; i < n; i++) {
if (f[i].size() == 1) {
s.insert(i);
}
}
mark(0, -1);
for (int i = 0; i < n; i++) {
assert(val[i] != -1);
MessageBoard(i, X >> val[i] & 1);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
namespace ioi {
const int MAX_BIT = 60;
int n;
vector<vector<int>> e, adj;
vector<bool> vis;
void dfs(int u) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) {
e[u].push_back(v);
e[v].push_back(u);
dfs(v);
}
}
}
int cnt = 0;
set<int> s;
vector<set<int>> f;
vector<int> val(n);
void find(int u, int p) {
val[u] = cnt++;
if (cnt == MAX_BIT) {
return;
}
for (int v : e[u]) {
if (v != p) {
f[u].insert(v);
f[v].insert(u);
find(v, u);
if (cnt == MAX_BIT)
return;
}
}
}
void mark(int u, int p) {
bool in = false, op1 = false, op2 = false;
int x = -1, to = -1;
if (val[u] == -1) {
in = true;
auto t = s.begin();
if (*t == p) t++;
x = *t;
to = *f[x].begin();
s.erase(x);
f[x].erase(to);
f[to].erase(x);
if (f[to].size() == 1) {
op1 = true;
s.insert(to);
}
if (f[p].size() == 1) {
op2 = true;
s.erase(p);
}
f[p].insert(u);
f[u].insert(p);
s.insert(u);
val[u] = val[x];
}
for (int v : e[u]) {
if (v != p) {
mark(v, u);
}
}
if (in) {
s.erase(u);
f[p].erase(u);
f[u].erase(p);
if (op2) {
s.insert(p);
}
if (op1) {
s.erase(to);
}
f[x].insert(to);
f[to].insert(x);
s.insert(x);
}
}
vector<bool> h(MAX_BIT);
i64 ans = 0;
void get(int u) {
for (int v : e[u]) {
if (!h[val[v]]) {
int x = Move(v);
ans |= (1LL * x) << val[v];
h[val[v]] = true;
get(v);
Move(u);
}
}
}
};
using namespace ioi;
long long Ioi(int N, int M, int A[], int B[], int u, int V, int T) {
n = N;
adj.resize(n);
e.resize(n);
for (int i = 0; i < M; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vis.assign(n, 0);
dfs(0);
f.resize(n);
val.resize(n, -1);
find(0, -1);
for (int i = 0; i < n; i++) {
if (f[i].size() == 1) {
s.insert(i);
}
}
mark(0, -1);
h[val[u]] = 0;
ans = (1LL * V) << val[u];
get(u);
return ans;
}
