#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Joi(int n, int m, int a[], int b[], ll x, int T){
if(T == 1){
for(int i = 0; i < 60; i++){
MessageBoard(i, bool(1LL << i & x));
}
for(int i = 60; i < n; i++){
MessageBoard(i, 0);
}
}
else if(T == 3){
for(int i = 0; i < n; i++){
MessageBoard(i, bool(1LL << (i % 60) & x));
}
}
else{
vector<vector<int>>g(n);
for(int i = 0; i < m; i++){
g[a[i]].emplace_back(b[i]);
g[b[i]].emplace_back(a[i]);
}
vector<int>id(n, -1);
int bit = 0;
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
if((id[s] = bit++) == 59){
bit = 0;
}
for(int& d : g[s]){
if(d != p && id[d] == -1){
dfs(d, s);
}
}
};
dfs(0, -1);
for(int i = 0; i < n; i++){
MessageBoard(i, bool(1LL << id[i] & x));
}
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Ioi(int n, int m, int a[], int b[], int p, int V, int T){
vector<vector<int>>g(n);
for(int i = 0; i < m; i++){
g[a[i]].emplace_back(b[i]);
g[b[i]].emplace_back(a[i]);
}
if(T == 1){
ll ans = 0;
vector<int>path, need_path;
vector<bool>vis(n);
function<void(int, const int)>dfs;
dfs = [&] (int s, const int destination){
path.emplace_back(s);
if(s == destination){
need_path = path;
}
vis[s] = true;
for(int& d : g[s]){
if(!vis[d]){
dfs(d, destination);
}
}
path.pop_back();
};
for(int i = 0; i < 60; i++){
fill(vis.begin(), vis.end(), false);
dfs(p, i);
for(int j = 1; j < need_path.size(); j++){
V = Move(p = need_path[j]);
}
if(V == 1){
ans |= 1LL << i;
}
}
return ans;
}
else if(T == 3){
while(p + 1 < n && p % 60 != 59){
V = Move(++p);
}
while(p % 60 != 59){
V = Move(--p);
}
ll ans = (V == 1 ? (1LL << 59) : 0);
for(int i = 58; i > -1; i--){
V = Move(--p);
if(V == 1){
ans |= 1LL << i;
}
}
return ans;
}
vector<int>tour, id(n, -1);
set<pair<int, int>>edge;
for(int i = 0; i < m; i++){
edge.insert(make_pair(a[i], b[i]));
edge.insert(make_pair(b[i], a[i]));
}
int cnt_bit = 0;
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
if((id[s] = cnt_bit++) == 59){
cnt_bit = 0;
}
tour.emplace_back(s);
for(int& d : g[s]){
if(d != p && id[d] == -1){
dfs(d, s);
tour.emplace_back(s);
}
}
};
dfs(0, -1);
int pos, cnt_move = 120;
for(int i = 0; i < tour.size(); i++){
if(tour[i] == p){
pos = i;
break;
}
}
vector<int>bit(60);
bit[id[p]] = V;
while(++pos < tour.size() && cnt_move-- > 0){
if(edge.find(make_pair(tour[pos - 1], tour[pos])) == edge.end()){
return 1;
}
bit[id[tour[pos]]] = Move(tour[pos]);
}
pos--;
while(cnt_move-- > 0){
pos--;
if(edge.find(make_pair(tour[pos + 1], tour[pos])) == edge.end()){
return 1;
}
bit[id[tour[pos]]] = Move(tour[pos]);
}
ll ans = 0;
for(int i = 0; i < 60; i++){
if(bit[i] == 1){
ans |= 1LL << i;
}
}
return ans;
}
