#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
#include "Joi.h"
#define all(x) begin(x), end(x)
#define f first
#define s second
using int2 = pair<int, int>;
// communicate 60 bits of information in 120 moves
struct DSU {
v<int> e;
DSU(int n) { e = v<int>(n, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
if (e[x] > e[y]) {
swap(x, y);
}
e[x] += e[y];
e[y] = x;
return true;
}
};
void Joi(int N, int M, int A[], int B[], long long X, int T) {
v<int> depth(N);
v<v<int>> adj(N);
DSU dsu(N);
for (int i = 0; i < M; i++) {
if (dsu.unite(A[i], B[i])) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
auto dfs = [&](int u, int p, auto &&dfs) -> void {
for (int v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u, dfs);
}
}
};
dfs(0, -1, dfs);
int U = max_element(all(depth)) - depth.begin();
depth.assign(N, 0);
dfs(U, -1, dfs);
int V = max_element(all(depth)) - depth.begin();
int d = depth[V];
if (d >= 60) {
for (int i = 0; i < N; i++) {
MessageBoard(i, (X >> (depth[i] % 60)) & 1);
}
} else {
int r = find(all(depth), d / 2) - depth.begin();
v<int> len(N);
auto dfs_len = [&](int u, int p, auto &&dfs_len) -> void {
for (int v : adj[u]) {
if (v != p) {
dfs_len(v, u, dfs_len);
len[u] = max(len[u], len[v] + 1);
}
}
};
dfs_len(U, -1, dfs_len);
v<int> num(N, -1);
int cnt = 0;
auto dfs = [&](int u, int p, auto &&dfs) -> void {
if (cnt < 60) {
num[u] = cnt++;
}
v<int2> ch;
for (int v : adj[u]) {
if (v != p) {
ch.push_back({len[v], v});
}
}
sort(all(ch), greater<int2>());
for (auto v : ch) {
dfs(v.s, u, dfs);
}
};
dfs(r, -1, dfs);
for (int i = 0; i < N; i++) {
if (num[i] != -1) {
MessageBoard(i, (X >> num[i]) & 1);
} else {
MessageBoard(i, 0);
}
}
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
#define all(x) begin(x), end(x)
using int2 = pair<int, int>;
using ll = long long;
#define f first
#define s second
// communicate 60 bits of information in 120 moves
struct DSU {
v<int> e;
DSU(int n) { e = v<int>(n, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
if (e[x] > e[y]) {
swap(x, y);
}
e[x] += e[y];
e[y] = x;
return true;
}
};
long long Ioi(int N, int M, int A[], int B[], int P, int VI, int T) {
v<int> depth(N);
v<v<int>> adj(N);
DSU dsu(N);
for (int i = 0; i < M; i++) {
if (dsu.unite(A[i], B[i])) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
v<int> up(N, -1);
auto dfs = [&](int u, int p, auto &&dfs) -> void {
up[u] = p;
for (int v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u, dfs);
}
}
};
dfs(0, -1, dfs);
int U = max_element(all(depth)) - depth.begin();
depth.assign(N, 0);
dfs(U, -1, dfs);
int V = max_element(all(depth)) - depth.begin();
int d = depth[V];
if (d >= 60) {
if (depth[P] >= 60) {
cerr << "case 1\n";
ll ans = 0;
for (int _ = 0; _ < 60; _++) {
ans ^= (ll)VI << (depth[P] % 60);
P = up[P];
VI = Move(P);
}
return ans;
} else {
cerr << "case 2\n";
while (P != U) {
P = up[P];
VI = Move(P);
}
v<int> down(N, -1);
auto path = [&](int u, int p, auto &&path) -> void {
for (int v : adj[u]) {
if (v != p) {
path(v, u, path);
if (v == V) {
down[u] = v;
} else if (down[v] != -1) {
down[u] = v;
}
}
}
};
path(P, -1, path);
ll ans = 0;
for (int i = 0; i < 60; i++) {
ans ^= (ll)VI << i;
P = down[P];
VI = Move(P);
}
return ans;
}
} else {
cerr << "case 3\n";
int r = find(all(depth), d / 2) - depth.begin();
v<int> len(N);
auto dfs_len = [&](int u, int p, auto &&dfs_len) -> void {
for (int v : adj[u]) {
if (v != p) {
dfs_len(v, u, dfs_len);
len[u] = max(len[u], len[v] + 1);
}
}
};
dfs_len(U, -1, dfs_len);
v<int> num(N, -1);
int cnt = 0;
auto dfs = [&](int u, int p, auto &&dfs) -> void {
up[u] = p;
if (cnt < 60) {
num[u] = cnt++;
}
v<int2> ch;
for (int v : adj[u]) {
if (v != p) {
ch.push_back({len[v], v});
}
}
sort(all(ch), greater<int2>());
for (auto v : ch) {
dfs(v.s, u, dfs);
}
};
dfs(r, -1, dfs);
while (P != r) {
P = up[P];
VI = Move(P);
}
cnt = 0;
ll ans = 0;
auto trav = [&](int u, int p, auto &&trav) -> void {
cnt++;
ans ^= (ll)VI << num[u];
v<int2> ch;
for (int v : adj[u]) {
if (v != p) {
ch.push_back({len[v], v});
}
}
sort(all(ch));
for (auto v : ch) {
if (num[v.s] != -1) {
VI = Move(v.s);
trav(v.s, u, trav);
if (cnt < 60) {
VI = Move(u);
}
}
}
};
trav(r, -1, trav);
return ans;
}
}
