#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
namespace joi{
#define int long long
const int N=1e4+10, M=2e4+10;
int n;
int m;
vector<int> g[N];
pair<int, int> edge[M];
int dep[N], par[N];
void dfs_dep(int u){
for (int v:g[u]) if (dep[v]==-1){
dep[v]=dep[u]+1;
par[v]=u;
dfs_dep(v);
}
}
int vis[N];
vector<int> chosen;
vector<int> diameter;
void dfs_choose(int u){
if ((int)chosen.size()==60) return;
for (int v:g[u]) if (!vis[v]){
if ((int)chosen.size()==60) return;
vis[v]=1;
chosen.push_back(v);
dfs_choose(v);
}
}
int ans[N];
void solve(int x){
memset(dep, -1, sizeof dep);
dep[0]=0; par[0]=-1; dfs_dep(0);
int u=max_element(dep, dep+n)-dep;
memset(dep, -1, sizeof dep);
dep[u]=0; par[u]=-1; dfs_dep(u);
int max_dep=*max_element(dep, dep+n);
if (max_dep>=60){
for (int i=0; i<n; ++i) MessageBoard(i, x>>(dep[i]%60)&1);
}else{
int v=max_element(dep, dep+n)-dep;
while (v!=u) chosen.push_back(v), v=par[v];
chosen.push_back(u);
reverse(chosen.begin(), chosen.end());
diameter=chosen;
for (int i:diameter) vis[i]=1;
for (int i:diameter) dfs_choose(i);
for (int i=0; i<60; ++i) ans[chosen[i]]=x>>i&1;
for (int i=0; i<n; ++i) MessageBoard(i, ans[i]);
}
}
#undef int
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
joi::n=N;
joi::m=M;
for (int i=0; i<M; ++i){
joi::g[A[i]].push_back(B[i]);
joi::g[B[i]].push_back(A[i]);
}
joi::solve(X);
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
namespace ioi{
#define int long long
const int N=1e4+10, M=2e4+10;
int n;
int m;
vector<int> g[N];
pair<int, int> edge[M];
int dep[N], par[N];
void dfs_dep(int u){
for (int v:g[u]) if (dep[v]==-1){
dep[v]=dep[u]+1;
par[v]=u;
dfs_dep(v);
}
}
int vis[N];
vector<int> chosen;
vector<int> diameter;
vector<int> gg[N];
void dfs_choose(int u){
if ((int)chosen.size()==60) return;
for (int v:g[u]) if (!vis[v]){
if ((int)chosen.size()==60) return;
vis[v]=1;
gg[u].push_back(v);
chosen.push_back(v);
dfs_choose(v);
}
}
int ans[N];
void dfs(int u){
if (find(diameter.begin(), diameter.end(), u)==diameter.end()){
for (int v:gg[u]){
if (find(chosen.begin(), chosen.end(), v)==chosen.end()) continue;
if (find(diameter.begin(), diameter.end(), v)==diameter.end()){
ans[v]=Move(v);
dfs(v);
Move(u);
}
}
return;
}
for (int v:gg[u]) if (v!=gg[u][0]){
if (find(chosen.begin(), chosen.end(), v)==chosen.end()) continue;
if (find(diameter.begin(), diameter.end(), v)==diameter.end()){
ans[v]=Move(v);
dfs(v);
Move(u);
}
}
if (gg[u].size()){
int v=gg[u][0];
ans[v]=Move(v);
return dfs(v);
}
}
int solve(int x, int y){
ans[x]=y;
memset(dep, -1, sizeof dep);
dep[0]=0; par[0]=-1; dfs_dep(0);
int u=max_element(dep, dep+n)-dep;
memset(dep, -1, sizeof dep);
dep[u]=0; par[u]=-1; dfs_dep(u);
int max_dep=*max_element(dep, dep+n);
if (max_dep>=60){
if (dep[x]>=59){
vector<int> path;
path.push_back(x);
while ((int)path.size()!=60){
x=par[x];
ans[x]=Move(x);
path.push_back(x);
}
int res=0;
for (int i:path) res|=ans[i]<<(dep[i]%60);
return res;
}
while (x!=u) x=par[x], ans[x]=Move(x);
int v=max_element(dep, dep+n)-dep;
vector<int> path;
while (v!=u) path.push_back(v), v=par[v];
path.push_back(u);
reverse(path.begin(), path.end());
path.resize(60);
for (int i=1; i<60; ++i) ans[path[i]]=Move(path[i]);
int res=0;
for (int i:path) res|=ans[i]<<(dep[i]%60);
return res;
}else{
int v=max_element(dep, dep+n)-dep;
while (v!=u) chosen.push_back(v), v=par[v];
chosen.push_back(u);
reverse(chosen.begin(), chosen.end());
diameter=chosen;
for (int i:diameter) vis[i]=1;
for (int i=0; i<(int)diameter.size()-1; ++i) gg[diameter[i]].push_back(diameter[i+1]);
for (int i:diameter) dfs_choose(i);
while (x!=u) x=par[x], ans[x]=Move(x);
dfs(x);
int res=0;
for (int i=0; i<60; ++i) res|=ans[chosen[i]]<<i;
return res;
}
return -1;
}
#undef int
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
ioi::n=N;
ioi::m=M;
for (int i=0; i<M; ++i){
ioi::g[A[i]].push_back(B[i]);
ioi::g[B[i]].push_back(A[i]);
}
return ioi::solve(P, V);
}
