#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), g(n);
vector<int>bit(n, -1);
for(int i = 0; i < m; i++){
_g[a[i]].emplace_back(b[i]);
_g[b[i]].emplace_back(a[i]);
}
function<void(int)>dfs;
dfs = [&] (int s){
bit[s] = -2;
for(int& d : _g[s]){
if(bit[d] == -1){
g[s].emplace_back(d);
g[d].emplace_back(s);
dfs(d);
}
}
};
dfs(0);
vector<int>T;
queue<int>q;
q.push(0);
for(int i = bit[0] = 0; i < 60; i++){
int u = q.front();
q.pop();
T.emplace_back(u);
MessageBoard(u, bool(1LL << (bit[u] = i) & x));
for(int& v : g[u]){
if(bit[v] == -2){
q.push(v);
bit[v] = -1;
}
}
}
vector<vector<int>>tree(n);
vector<pair<int, int>>to;
for(int& i : T){
tree[i] = T;
for(int& j : g[i]){
if(bit[j] < 0){
to.emplace_back(i, j);
bit[j] = 0;
}
}
}
while(!to.empty()){
auto [u, v] = to.back();
to.pop_back();
tree[v] = tree[u];
vector<int>d(n, 0);
vector<bool>mark(n, false);
for(int& i : tree[u]){
mark[i] = true;
}
for(int& i : tree[u]){
int d = 0;
for(int& j : g[i]){
if(mark[j]){
d++;
}
}
if(d == 1){
MessageBoard(v, bool(1LL << (bit[v] = bit[i]) & x));
tree[v].erase(find(tree[v].begin(), tree[v].end(), i));
tree[v].emplace_back(v);
break;
}
}
for(int& i : g[v]){
if(bit[i] < 0){
to.emplace_back(v, i);
bit[i] = 0;
}
}
}
}
}
#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 subtask){
if(subtask == 1){
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]);
}
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(subtask == 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<vector<int>>_g(n), g(n);
vector<int>bit(n, -1);
for(int i = 0; i < m; i++){
_g[a[i]].emplace_back(b[i]);
_g[b[i]].emplace_back(a[i]);
}
function<void(int)>dfs_0;
dfs_0 = [&] (int s){
bit[s] = -2;
for(int& d : _g[s]){
if(bit[d] == -1){
g[s].emplace_back(d);
g[d].emplace_back(s);
dfs_0(d);
}
}
};
dfs_0(0);
vector<int>T;
queue<int>q;
q.push(0);
for(int i = 0; i < 60; i++){
int u = q.front();
q.pop();
bit[u] = i;
T.emplace_back(u);
for(int& v : g[u]){
if(bit[v] == -2){
q.push(v);
bit[v] = -1;
}
}
}
vector<vector<int>>tree(n);
vector<pair<int, int>>to;
for(int& i : T){
tree[i] = T;
for(int& j : g[i]){
if(bit[j] < 0){
to.emplace_back(i, j);
bit[j] = 0;
}
}
}
while(!to.empty()){
auto [u, v] = to.back();
to.pop_back();
tree[v] = tree[u];
vector<int>d(n, 0);
vector<bool>mark(n, false);
for(int& i : tree[u]){
mark[i] = true;
}
for(int& i : tree[u]){
int d = 0;
for(int& j : g[i]){
if(mark[j]){
d++;
}
}
if(d == 1){
tree[v].erase(find(tree[v].begin(), tree[v].end(), i));
tree[v].emplace_back(v);
bit[v] = bit[i];
break;
}
}
for(int& i : g[v]){
if(bit[i] < 0){
to.emplace_back(v, i);
bit[i] = 0;
}
}
}
vector<bool>mark(n, false);
for(int& i : tree[p]){
mark[i] = true;
}
function<void(int)>dfs_1;
ll ans = (V == 0 ? 0 : (1LL << bit[p]));
dfs_1 = [&] (int s){
mark[s] = false;
for(int& d : g[s]){
if(mark[d]){
if(Move(d) == 1){
ans |= 1LL << bit[d];
}
dfs_1(d);
Move(s);
}
}
};
dfs_1(p);
return ans;
}
