#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
namespace JOI {
const int Z = 1e4;
int L[Z], R[Z], dfsTimer, d[Z], e[Z];
bool vis[Z];
vector<int> g[Z], h[Z];
long long x;
int init(int u) {
L[u] = 1;
for(const int &v : g[u]) if(!L[v]) {
e[v] = d[v] = d[u] + 1;
e[u] = max(e[u], init(v));
h[u].push_back(v);
}
sort(begin(h[u]), end(h[u]), [&](const int &i, const int &j) {
return e[i] > e[j];
});
return e[u];
}
void dfs(int u) {
L[u] = ++dfsTimer;
for(const int &v : h[u]) dfs(v);
R[u] = 1+dfsTimer;
MessageBoard(u, bool(x & (1LL<<(L[u] % 60))));
}
void Joi(int N, int M, int A[], int B[], long long X, int _T) {
x = X;
for(int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
init(0);
dfs(0);
}
};
void Joi(int N, int M, int A[], int B[], long long X, int _T) {
JOI::Joi(N, M, A, B, X, _T);
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
namespace IOI {
const int Z = 1e4;
int L[Z], R[Z], dfsTimer, d[Z], e[Z], p[Z];
bool vis[Z];
vector<int> g[Z], h[Z];
int init(int u) {
L[u] = ++dfsTimer;
for(const int &v : g[u]) if(!L[v]) {
p[v] = u;
e[v] = d[v] = d[u] + 1;
e[u] = max(e[u], init(v));
h[u].push_back(v);
}
sort(begin(h[u]), end(h[u]), [&](const int &i, const int &j) {
return e[i] > e[j];
});
R[u] = 1+dfsTimer;
return e[u];
}
int r;
vector<pair<int, int>> path;
#define valid(X) (L[r] <= X && X < L[r] + 60)
void dfs(int u) {
L[u] = ++dfsTimer;
for(const int &v : h[u]) {
if(valid(L[u]) && valid(dfsTimer+1))
path.emplace_back(u, v);
dfs(v);
if(valid(L[u]) && valid(L[v]))
path.emplace_back(v, u);
}
R[u] = 1+dfsTimer;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
init(0);
r = P;
while(R[r] - L[r] < 60) V = Move(r = p[r]);
dfs(dfsTimer = 0);
long long x {};
set<int> done;
done.insert(L[r] % 60);
if(V) x |= 1LL << (L[r] % 60);
while(size(done) < 60) {
auto [v, pos] = path.back();
path.pop_back();
done.insert(pos = L[v] % 60);
if(Move(r = v))
x |= 1LL << pos;
}
return x;
}
};
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
return IOI::Ioi(N, M, A, B, P, V, T);
}
