#include "bits/stdc++.h"
using namespace std;
#include "Joi.h"
const int N = 1e4 + 5;
vector<int> G[N], tt;
int used[N], d[N];
void dfs(int u){
used[u] = 1;
tt.push_back(u);
for(auto x : G[u]){
if(used[x]) continue;
d[x] = d[u] + 1;
dfs(x);
}
}
void Joi(int n, int m, int a[], int b[], long long x, int t) {
for(int i=0;i<m;i++){
G[a[i]].push_back(b[i]);
G[b[i]].push_back(a[i]);
} for(int i=0;i<n;i++){
sort(G[i].begin(), G[i].end());
}
d[0] = 1; dfs(0);
bool ok = 0;
for(int i=0;i<n;i++){
if(d[i] >= 60){
ok = 1;
} d[i] = (d[i] - 1) % 60;
}
if(ok){
for(int i=0;i<n;i++){;
MessageBoard(i, x >> d[i] & 1);
}
} else {
for(int i=0;i<min(n, 60);i++){
MessageBoard(tt[i], x >> i & 1);
} for(int i=60;i<n;i++){
MessageBoard(tt[i], 0);
}
}
}
#include "bits/stdc++.h"
using namespace std;
#include "Ioi.h"
const int N = 1e4 + 5;
int used[N], par[N], d[N];
vector<int> G[N], tt;
void dfs(int u){
used[u] = 1;
tt.push_back(u);
for(auto x : G[u]){
if(used[x]) continue;
d[x] = d[u] + 1,
par[x] = u, dfs(x);
tt.push_back(u);
}
}
long long Ioi(int n, int m, int a[], int b[], int p, int v, int t){
for(int i=0;i<m;i++){
G[a[i]].push_back(b[i]);
G[b[i]].push_back(a[i]);
} for(int i=0;i<n;i++){
sort(G[i].begin(), G[i].end());
}
d[0] = 1; dfs(0);
int r = -1;
for(int i=0;i<n;i++){
if(d[i] >= 60) r = i;
}
auto go = [&](int x){ bool ok = 0;
for(auto v : G[p]){
if(v == x) ok = 1;
} assert(ok);
v = Move(x), p = x;
};
long long x = 0;
if(~r){
if(d[p] >= 60){
for(int j=0;j<60;j++){ d[p] = (d[p] - 1) % 60;
if(v) x |= (1ll << d[p]);
if(p) go(par[p]);
} return x;
} else { tt.clear();
while(p) go(par[p]);
while(r) tt.push_back(r), r = par[r];
for(int i=0;i<60;i++){ d[p] = (d[p] - 1) % 60;
if(v) x |= (1ll << d[p]);
if(!tt.empty()){
go(tt.back());
tt.pop_back();
}
} return x;
}
}
while(p) go(par[p]);
memset(used, 0, sizeof used);
int cnt = 1; used[0] = 1;
assert(!tt[0]);
x |= v;
tt.erase(tt.begin(), tt.begin() + 1);
for(auto u : tt){
go(u);
if(used[u]) continue;
if(v) x |= (1ll << cnt);
used[u] = 1; cnt++;
if(cnt == 60) break;
}
return x;
}
