// Om Namah Shivaya
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a, b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a, b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "Joi.h"
static vector<int> adj[N];
static vector<int> cnt(N);
static vector<pii> group(N,{-1,-1});
static int ptr = 0;
static void build(int u){
trav(v,adj[u]){
if(group[v].ff != -1) conts;
int id = group[u].ff;
if(cnt[id] == 60){
id = ptr++;
}
group[v] = {id,cnt[id]++};
build(v);
}
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
rep(i,m){
int u = A[i], v = B[i];
adj[u].pb(v), adj[v].pb(u);
}
group[0] = {0,0};
cnt[0]++;
ptr++;
build(0);
rep(i,n){
int bit = group[i].ss;
int b = 0;
if(X & (1ll<<bit)) b = 1;
MessageBoard(i,b);
}
}
// Om Namah Shivaya
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a, b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a, b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e4 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "Ioi.h"
static vector<int> adj[N];
static vector<int> cnt(N);
static vector<pii> group(N,{-1,-1});
static int ptr = 0;
static void build(int u){
trav(v,adj[u]){
if(group[v].ff != -1) conts;
int id = group[u].ff;
if(cnt[id] == 60){
id = ptr++;
}
group[v] = {id,cnt[id]++};
build(v);
}
}
vector<int> adj2[60];
vector<bool> vis(60);
vector<int> actual_nodes(60);
vector<int> depth(60), deepest(60);
ll x_val = 0;
void dfs1(int u){
vis[u] = 1;
deepest[u] = depth[u];
trav(v,adj2[u]){
if(vis[v]) conts;
depth[v] = depth[u]+1;
dfs1(v);
amax(deepest[u],deepest[v]);
}
}
void dfs2(int u, int ret){
vis[u] = 1;
pii best = {-1,-1};
trav(v,adj2[u]){
if(vis[v]) conts;
pii px = {deepest[v],v};
amax(best,px);
}
trav(v,adj2[u]){
if(vis[v]) conts;
if(!ret and v == best.ss) conts;
int b = Move(actual_nodes[v]);
int bit = v;
if(b) x_val |= (1ll<<bit);
dfs2(v,1);
Move(actual_nodes[u]);
}
if(!ret and best.ss != -1){
int v = best.ss;
int b = Move(actual_nodes[v]);
int bit = v;
if(b) x_val |= (1ll<<bit);
dfs2(v,0);
}
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
rep(i,m){
int u = A[i], v = B[i];
adj[u].pb(v), adj[v].pb(u);
}
group[0] = {0,0};
cnt[0]++;
ptr++;
build(0);
// find closest good group
queue<int> q2;
vector<int> par(n,-1);
q2.push(P);
par[P] = P;
int want = -1;
while(!q2.empty()){
int u = q2.front();
q2.pop();
int c = group[u].ff;
if(cnt[c] == 60){
want = u;
break;
}
trav(v,adj[u]){
if(par[v] == -1){
q2.push(v);
par[v] = u;
}
}
}
assert(want != -1);
int root = group[want].ss;
int root_val = V;
vector<int> path;
int o_want = want;
while(want != P){
path.pb(want);
want = par[want];
}
reverse(all(path));
trav(u,path){
root_val = Move(u);
P = u;
}
want = o_want;
assert(P == want);
int want_col = group[want].ff;
rep(u,n){
if(group[u].ff == want_col){
actual_nodes[group[u].ss] = u;
}
}
rep(u,n){
trav(v,adj[u]){
if(group[u].ff == want_col and group[v].ff == want_col){
int x = group[u].ss;
int y = group[v].ss;
adj2[x].pb(y);
adj2[y].pb(x);
}
}
}
if(root_val) x_val |= (1ll<<root);
dfs1(root);
fill(all(vis),0);
dfs2(root,0);
return x_val;
}
