#include "Joi.h"
#include "bits/stdc++.h"
using namespace std;
namespace {
const int maxn = 1e4 + 4;
vector<int> g[maxn];
vector<int> adj[maxn];
int n;
int m;
int par[maxn];
int h[maxn];
int tin[maxn], timer, et[maxn];
int sz[maxn];
int mx[maxn];
pair<int, int> bfs(int src) {
queue<int> q;
vector<int> d(n + 1, -1);
d[src] = 0;
par[src] = 0;
q.push(src);
memset(par, -1, sizeof(par));
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
par[v] = u;
q.push(v);
}
}
}
int mx = *max_element(d.begin(), d.end());
return make_pair(mx, src);
}
void pre_dfs(int u, int prev = -1) {
sz[u] = 1;
mx[u] = 1;
for (auto v : adj[u]) {
if (v == prev) continue;
h[v] = h[u] + 1;
par[v] = u;
pre_dfs(v, u);
sz[u] += sz[v];
mx[u] = max(mx[u], mx[v] + 1);
}
}
int find_centroid(int u, int prev, int n) {
for (auto v : adj[u]) {
if (v == prev) continue;
if (sz[v] * 2 > n) return find_centroid(v, u, n);
}
return u;
}
void dfs(int u, int prev = -1) {
// int big_child = -1;
// for (int i = 0; i < (int)adj[u].size(); ++i) {
// if (adj[u][i] == prev) continue;
// if (big_child == -1 || mx[adj[u][i]] > mx[adj[u][big_child]]) {
// big_child = i;
// }
// }
// if (big_child != -1) {
// swap(adj[u][0], adj[u][big_child]);
// }
sort(adj[u].begin(), adj[u].end(), [](const int &x, const int &y) -> bool {
if (n > 80) {
return mx[x] > mx[y];
}
return sz[x] < sz[y];
});
tin[u] = ++timer;
et[timer] = u;
for (auto v : adj[u]) {
if (v == prev) continue;
dfs(v, u);
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n = N, m = M;
for (int i = 0; i < n; ++i) {
g[i].clear();
adj[i].clear();
}
for (int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
pair<int, int> opt = bfs(0);
for (int i = 0; i < n; ++i) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
h[i] = h[par[i]] + 1;
}
}
int r = max_element(h, h + n) - h;
h[r] = 0;
par[r] = -1;
pre_dfs(r);
timer = 0;
dfs(r);
opt.first = *max_element(h, h + n);
if (opt.first + 1 >= 60) {
for (int i = 0; i < n; ++i) {
MessageBoard(i, X >> (h[i] % 60) & 1);
}
} else {
int c = find_centroid(r, 0, n);
h[c] = 0;
par[c] = -1;
timer = 0;
pre_dfs(c); dfs(c);
for (int i = 0; i < n; ++i) {
MessageBoard(et[i + 1], X >> (i % 60) & 1);
}
}
}
#include "Ioi.h"
#include "bits/stdc++.h"
using namespace std;
namespace {
const int maxn = 1e4 + 4;
vector<int> g[maxn];
vector<int> adj[maxn];
int n;
int m;
int par[maxn];
int h[maxn];
int mx[maxn];
int tin[maxn], timer, et[maxn];
int sz[maxn];
long long x;
pair<int, int> bfs(int src) {
queue<int> q;
vector<int> d(n + 1, -1);
d[src] = 0;
par[src] = 0;
q.push(src);
memset(par, -1, sizeof(par));
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) {
if (d[v] == -1) {
d[v] = d[u] + 1;
par[v] = u;
q.push(v);
}
}
}
int mx = *max_element(d.begin(), d.end());
return make_pair(mx, src);
}
void pre_dfs(int u, int prev = -1) {
sz[u] = 1;
mx[u] = 1;
for (auto v : adj[u]) {
if (v == prev) continue;
h[v] = h[u] + 1;
par[v] = u;
pre_dfs(v, u);
sz[u] += sz[v];
mx[u] = max(mx[u], mx[v] + 1);
}
}
void dfs(int u, int prev = -1) {
// int big_child = -1;
// for (int i = 0; i < (int)adj[u].size(); ++i) {
// if (adj[u][i] == prev) continue;
// if (big_child == -1 || mx[adj[u][i]] > mx[adj[u][big_child]]) {
// big_child = i;
// }
// }
// if (big_child != -1) {
// swap(adj[u][0], adj[u][big_child]);
// }
sort(adj[u].begin(), adj[u].end(), [](const int &x, const int &y) -> bool {
if (n > 80) {
return mx[x] > mx[y];
}
return sz[x] < sz[y];
});
tin[u] = ++timer;
et[timer] = u;
for (auto v : adj[u]) {
if (v == prev) continue;
dfs(v, u);
}
}
int find_centroid(int u, int prev, int n) {
for (auto v : adj[u]) {
if (v == prev) continue;
if (sz[v] * 2 > n) return find_centroid(v, u, n);
}
return u;
}
bool done;
void traverse(int u, int prev = -1) {
if (done) return;
if (tin[u] == 60) {
done = 1;
return;
}
for (auto v : adj[u]) {
if (v == prev) continue;
if (done) return;
int nxt = Move(v);
if (nxt) {
x |= (1ll << (tin[v] - 1));
}
traverse(v, u);
if (done) return;
}
if (par[u] != -1) {
Move(par[u]);
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
n = N, m = M;
for (int i = 0; i < n; ++i) {
g[i].clear();
adj[i].clear();
}
for (int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
pair<int, int> opt = bfs(0);
for (int i = 0; i < n; ++i) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
h[i] = h[par[i]] + 1;
}
}
int r = max_element(h, h + n) - h;
h[r] = 0;
par[r] = -1;
pre_dfs(r);
timer = 0;
dfs(r);
opt.first = *max_element(h, h + n);
if (opt.first + 1 >= 60) {
if (h[P] >= 59) {
x = 0;
vector<int> hehe(60);
hehe[h[P] % 60] = V;
for (int i = 1; i < 60; ++i) {
assert(par[P] != -1);
hehe[h[par[P]] % 60] = Move(par[P]);
P = par[P];
}
for (int i = 0; i < 60; ++i) {
if (hehe[i]) x |= (1ll << i);
}
return x;
}
x = V;
while (par[P] != -1) {
int nxt = Move(par[P]);
if (par[par[P]] == -1) {
x = nxt;
}
P = par[P];
}
for (int i = 0; i < 59; ++i) {
int v = -1;
for (auto x : adj[P]) {
if (x == par[P]) continue;
if (v == -1 || mx[x] > mx[v]) v = x;
}
if (Move(v)) {
x |= (1ll << h[v]);
}
P = v;
}
return x;
} else {
int c = find_centroid(r, 0, n);
h[c] = 0;
par[c] = -1;
timer = 0;
pre_dfs(c); dfs(c);
x = V;
int cnt = 0;
while (par[P] != -1) {
++cnt;
int nxt = Move(par[P]);
if (par[par[P]] == -1) {
x = nxt;
}
P = par[P];
}
cerr << "cost " << cnt << endl;
done = 0;
traverse(P);
return x;
}
}
