#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
bitset<10000> G[10000];
vector<int> g[10000];
bool vis[10000];
int pos[10000], pr[10000], c[10000];
int timer = 0;
void dfs(int u) {
vis[u] = 1;
pos[timer++] = u;
for (int v : g[u]) {
if (!vis[v]) {
pr[v] = u;
dfs(v);
}
}
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for (int i = 0; i < M; ++i) {
G[A[i]][B[i]] = 1;
G[B[i]][A[i]] = 1;
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs(0);
vector<int> tr;
for (int i = 0; i < 60; ++i) {
tr.push_back(pos[i]);
c[pos[i]] = i;
}
vector<vector<int>> tree(N);
for (int u : tr) {
tree[u] = tr;
}
for (int i = 60; i < N; ++i) {
int u = pos[i], p = pr[u];
auto &tr = tree[u];
tr = tree[p];
int d = -1;
for (int x : tr) {
if (x != p) {
int deg = 0;
for (int y : tr) {
if (G[x][y]) {
++deg;
}
}
if (deg == 1) {
d = x;
break;
}
}
}
c[u] = c[d];
tr.erase(find(tr.begin(), tr.end(), d));
tr.push_back(u);
}
for (int i = 0; i < N; ++i) {
MessageBoard(i, X >> c[i] & 1);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
void __print() {
cerr << "]\n";
}
template<class T, class... V>
void __print(T t, V... v) {
cerr << t;
if (sizeof...(v)) {
cerr << ", ";
}
__print(v...);
}
#define debug(x...) cerr << "[" << #x << "] = ["; __print(x);
bitset<10000> G[10000];
vector<int> g[10000], gph[10000];
bool vis[10000];
int pos[10000], pr[10000], c[10000], val[10000];
int timer = 0;
void dfs(int u) {
vis[u] = 1;
pos[timer++] = u;
for (int v : g[u]) {
if (!vis[v]) {
pr[v] = u;
dfs(v);
}
}
}
void DFS(int u) {
vis[u] = 1;
for (int v : gph[u]) {
if (!vis[v]) {
val[v] = Move(v);
DFS(v);
Move(u);
}
}
}
}
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]][B[i]] = 1;
G[B[i]][A[i]] = 1;
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs(0);
vector<int> tr;
for (int i = 0; i < 60; ++i) {
tr.push_back(pos[i]);
c[pos[i]] = i;
}
vector<vector<int>> tree(N);
for (int u : tr) {
tree[u] = tr;
}
for (int i = 60; i < N; ++i) {
int u = pos[i], p = pr[u];
auto &tr = tree[u];
tr = tree[p];
int d = -1;
for (int x : tr) {
if (x != p) {
int deg = 0;
for (int y : tr) {
if (G[x][y]) {
++deg;
}
}
if (deg == 1) {
d = x;
break;
}
}
}
c[u] = c[d];
tr.erase(find(tr.begin(), tr.end(), d));
tr.push_back(u);
}
val[P] = V;
for (int x : tree[P]) {
for (int y : tree[P]) {
if (G[x][y]) {
gph[x].push_back(y);
gph[y].push_back(x);
}
}
}
fill(vis, vis + N, 0);
DFS(P);
long long res = 0;
for (int x : tree[P]) {
if (val[x]) {
res += 1LL << c[x];
}
}
return res;
}
