#include <bits/stdc++.h>
#include "Joi.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 1e6+10,mod = 1e9+7;
vector<int> aadj[N];
int TT,ttin[N];
bool vvis[N];
void dfs(int v,ll x){
if ((x&(1ll << (TT%60)))) MessageBoard(v,1);
else MessageBoard(v,0);
ttin[v] = TT++;
vvis[v] = 1;
for (int u : aadj[v]) if (!vvis[u]) dfs(u,x);
}
void Joi(int n, int m, int A[], int B[], long long x, int tt) {
rep(i,0,m){
aadj[A[i]].pb(B[i]);
aadj[B[i]].pb(A[i]);
}
rep(i,0,n) sort(all(aadj[i]));
dfs(0,x);
return;
}
#include "Ioi.h"
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 1e6+10,mod = 1e9+7;
constexpr ll inf = 1e9+10;
vector<int> adj[N];
bool vis[N];
int tin[N],T;
int par[N],ans[70];
int po[N];
void dfs(int v){
vis[v] = 1;
tin[v] = T++;
for (int u : adj[v]) if (!vis[u]){
par[u] = v;
dfs(u);
}
}
long long Ioi(int n, int m, int A[], int B[], int P, int v, int tt) {
rep(i,0,m){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
rep(i,0,n) sort(all(adj[i]));
dfs(0);
memset(ans,-1,sizeof ans);
swap(P,v);
int cur = v;
ans[tin[cur]%60] = P;
int cnt = 1;
while (cnt < 60){
int fl = -1;
int sz = adj[cur].size();
while (po[cur] < sz){
int u = adj[cur][po[cur]];
po[cur]++;
if (u == par[cur]) continue;
if (ans[tin[u]%60] != -1) continue;
fl = u;
}
if (fl == -1)
fl = par[cur];
int t = tin[fl]%60;
if (ans[t] == -1) cnt++;
ans[t] = Move(fl);
cur = fl;
}
ll out = 0;
rep(i,0,60) if (ans[i]) out += (1ll << i);
return out;
}
