#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 par[maxn];
int h[maxn];
int tin[maxn], timer, et[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 dfs(int u) {
tin[u] = ++timer;
et[timer] = u;
for (auto v : adj[u]) {
h[v] = h[u] + 1;
dfs(v);
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
pair<int, int> opt = make_pair(-1, -1);
pair<int, int> mn = make_pair(1e9, 1e9);
n = N;
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]);
}
for (int i = 0; i < n; ++i) {
pair<int, int> cur = bfs(i);
opt = max(opt, cur);
mn = min(mn, cur);
}
if (opt.first + 1 >= 60) {
bfs(opt.second);
for (int i = 0; i < n; ++i) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
}
}
dfs(opt.second);
for (int i = 0; i < n; ++i) {
MessageBoard(i, X >> (h[i] % 60) & 1);
}
} else {
// cerr << mn.first << " " << mn.second << endl;
bfs(mn.second);
for (int i = 0; i < n; ++i) {
// cerr << i << " " << par[i] << endl;
if (par[i] != -1) {
adj[par[i]].push_back(i);
}
}
timer = 0;
dfs(mn.second);
for (int i = 0; i < n; ++i) {
// cerr << et[i + 1] << " ";
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 par[maxn];
int h[maxn];
int mx[maxn];
int tin[maxn], timer, et[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 dfs(int u) {
tin[u] = ++timer;
et[timer] = u;
for (auto v : adj[u]) {
h[v] = h[u] + 1;
dfs(v);
}
}
void dfs_mx(int u) {
mx[u] = 1;
for (auto v : adj[u]) {
dfs_mx(v);
mx[u] = max(mx[u], mx[v] + 1);
}
}
bool done;
void traverse(int u) {
if (done) return;
if (tin[u] == 60) {
done = 1;
return;
}
// cerr << "at " << u << " " << tin[u] << endl;
for (auto v : adj[u]) {
if (done) return;
int nxt = Move(v);
if (nxt) {
x |= (1ll << (tin[v] - 1));
}
// cerr << "Y " << u << " " << v << endl;
traverse(v);
if (done) return;
}
if (par[u] != -1) {
Move(par[u]);
// cerr << "X " << u << " " << par[u] << endl;
}
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
pair<int, int> opt = make_pair(-1, -1);
pair<int, int> mn = make_pair(1e9, 1e9);
n = N;
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]);
}
for (int i = 0; i < n; ++i) {
pair<int, int> cur = bfs(i);
opt = max(opt, cur);
mn = min(mn, cur);
}
if (opt.first + 1 >= 60) {
bfs(opt.second);
for (int i = 0; i < n; ++i) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
}
}
timer = 0;
dfs(opt.second);
if (h[P] >= 59) {
x = V;
for (int i = 1; i < 60; ++i) {
assert(par[P] != -1);
// cerr << "E " << P << " " << par[P] << endl;
x |= (1ll << (Move(par[P])));
P = par[P];
}
return x;
}
x = 0;
while (par[P] != -1) {
int nxt = Move(par[P]);
if (par[par[P]] == -1) {
x = nxt;
}
P = par[P];
}
dfs_mx(P);
// cerr << "root " << P << endl;
for (int i = 0; i < 59; ++i) {
int v = -1;
for (auto x : adj[P]) {
if (v == -1 || mx[x] > mx[v]) v = x;
}
if (Move(v)) {
x |= (1ll << h[v]);
}
P = v;
}
return x;
} else {
bfs(mn.second);
for (int i = 0; i < n; ++i) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
}
}
// cerr << "HELO" << endl;
timer = 0;
dfs(mn.second);
while (par[P] != -1) {
int nxt = Move(par[P]);
if (par[par[P]] == -1) {
x = nxt;
}
P = par[P];
}
// cerr << "ROOT " << P << endl;
done = 0;
traverse(P);
return x;
}
}
