#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> G[10101];
vector<int> adj[10101];
bool vst[10101];
int C[10101];
int W[10101];
int cid;
vector<int> tre[10101];
int cnt;
void init(int x) {
vst[x] = true;
for(int i : G[x]) {
if(vst[i]) continue;
adj[x].push_back(i);
adj[i].push_back(x);
init(i);
}
}
void dfs(int x, int p) {
cnt++;
tre[cid].push_back(x);
C[x] = cid;
for(int i : adj[x]) {
if(cnt >= 60) break;
if(i == p) continue;
dfs(i, x);
}
}
void dfs2(int x, int p, int c) {
tre[cid].push_back(x);
cnt++;
for(int i : adj[x]) {
if(cnt >= 60) break;
if(C[i] != c) continue;
if(i == p) continue;
dfs2(i, x, c);
}
}
void mk(int x, int p) {
cid++;
cnt = 0;
dfs(x, p);
if(tre[cid].size() < 60) {
dfs2(p, -1, C[p]);
}
}
void sol(int x, int p) {
if(!C[x]) mk(x, p);
for(int i : adj[x]) {
if(i != p) sol(i, x);
}
}
bool used[66];
void Joi(int N, int M, int A[], int B[], long long X, int T) {
for(int i = 0; i < N; i++) W[i] = 60;
for(int i = 0; i < M; i++) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
init(0);
sol(0, -1);
for(int i = 1; i <= cid; i++) {
for(int j = 0; j < 60; j++) used[j] = false;
for(int j : tre[i]) used[W[j]] = true;
int p = 0;
for(int j : tre[i]) {
if(W[j] < 60) continue;
while(used[p]) p++;
W[j] = p;
used[p] = true;
}
}
for(int i = 0; i < N; i++) MessageBoard(i, (X & ((1ll) << W[i])) > 0);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
struct XX {
vector<int> G[10101];
vector<int> adj[10101];
bool vst[10101];
int C[10101];
int W[10101];
int cid;
vector<int> tre[10101];
int cnt;
void init(int x) {
vst[x] = true;
for(int i : G[x]) {
if(vst[i]) continue;
adj[x].push_back(i);
adj[i].push_back(x);
init(i);
}
}
void dfs(int x, int p) {
cnt++;
tre[cid].push_back(x);
C[x] = cid;
for(int i : adj[x]) {
if(cnt >= 60) break;
if(i == p) continue;
dfs(i, x);
}
}
void dfs2(int x, int p, int c) {
tre[cid].push_back(x);
cnt++;
for(int i : adj[x]) {
if(cnt >= 60) break;
if(C[i] != c) continue;
if(i == p) continue;
dfs2(i, x, c);
}
}
void mk(int x, int p) {
cid++;
cnt = 0;
dfs(x, p);
if(tre[cid].size() < 60) {
dfs2(p, -1, C[p]);
}
}
void sol(int x, int p) {
if(!C[x]) mk(x, p);
for(int i : adj[x]) {
if(i != p) sol(i, x);
}
}
bool used[66];
}XXX;
int ans[66];
int c;
void trav(int x, int p) {
for(int i : XXX.adj[x]) {
if(i == p) continue;
bool ok = false;
for(int j : XXX.tre[c]) if(j == i) ok = true;
if(!ok) continue;
ans[XXX.W[i]] = Move(i);
trav(i, x);
}
if(p != -1) Move(p);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
for(int i = 0; i < N; i++) XXX.W[i] = 60;
for(int i = 0; i < M; i++) {
XXX.G[A[i]].push_back(B[i]);
XXX.G[B[i]].push_back(A[i]);
}
XXX.cid = 0;
XXX.init(0);
XXX.sol(0, -1);
for(int i = 1; i <= XXX.cid; i++) {
for(int j = 0; j < 60; j++) XXX.used[j] = false;
for(int j : XXX.tre[i]) XXX.used[XXX.W[j]] = true;
int p = 0;
for(int j : XXX.tre[i]) {
if(XXX.W[j] < 60) continue;
while(XXX.used[p]) p++;
XXX.W[j] = p;
XXX.used[p] = true;
}
}
ans[XXX.W[P]] = V;
c = XXX.C[P];
trav(P, -1);
long long ret = 0;
for(int i = 0; i < 60; i++) if(ans[i]) ret += ((1ll) << i);
return ret;
}
