#include "Joi.h"
#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <class S> using pq = priority_queue<S,vector<S>,greater<S>>;
template <class S,class T> inline bool chmax(S &a,const T&b) { return (a < b)?a=b,1:0; }
template <class S,class T> inline bool chmin(S &a,const T&b) { return (a > b)?a=b,1:0; }
#define overlord3(_a,_b,_c,_d,name,...) name
#define REP1(i,n) for(ll i = 0; i < (n); i++)
#define REP2(i,a,b) for(ll i = (a); i < (b); i++)
#define REP3(i,a,b,c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overlord3(__VA_ARGS__,REP3,REP2,REP1)(__VA_ARGS__)
#define PER1(i,n) for(ll i = (n)-1; i >= 0; i--)
#define PER2(i,a,b) for(ll i = (a)-1; i >= b; i--)
#define PER3(i,a,b,c) for(ll i = (a)-1; i >= b; i -= c)
#define per(...) overlord3(__VA_ARGS__,PER3,PER2,PER1)(__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
#define si(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define lb(c,x) distance((c).begin(),lower_bound(all(c),x))
#define ub(c,x) distance((c).begin(),upper_bound(all(c),x))
#define SORT(c) sort(all(c))
#define REV(c) reverse(all(c))
#define UNIQUE(c) SORT(c),c.erase(unique(all(c)),c.end())
void Joi(int N, int M, int A[], int B[], long long X, int T) {
vvc<int>road(N);
rep(i,M) {
road[A[i]].pb(B[i]);
road[B[i]].pb(A[i]);
}
vvc<int>ki(N);
{
vc<int>used(N);
auto dfs = [&](auto &dfs,int n) -> void {
used[n] = 1;
for(auto i:road[n]) {
if(!used[i]) {
ki[n].pb(i);
dfs(dfs,i);
}
}
};
dfs(dfs,0);
}
vc<int>f(N);
{
auto dfs = [&](auto &dfs,int n) -> int {
int res = 1;
for(auto i:ki[n]) {
res += dfs(dfs,i);
}
if(res >= 60) {
f[n] = 1;
return 0;
}
else {
return res;
}
};
dfs(dfs,0);
}
vc<int>col(N);
rep(i,N) {
if(!f[i]) continue;
vc<int>id;
auto dfs = [&](auto &dfs,int n) -> void {
id.pb(n);
for(auto i:ki[n]) {
if(f[i]) continue;
dfs(dfs,i);
}
};
dfs(dfs,i);
rep(j,60) {
col[id[j]] = 1 & (X >> j);
}
}
rep(i,N) {
MessageBoard(i,col[i]);
}
}
#include "Ioi.h"
#include <string.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <class S> using pq = priority_queue<S,vector<S>,greater<S>>;
template <class S,class T> inline bool chmax(S &a,const T&b) { return (a < b)?a=b,1:0; }
template <class S,class T> inline bool chmin(S &a,const T&b) { return (a > b)?a=b,1:0; }
#define overlord3(_a,_b,_c,_d,name,...) name
#define REP1(i,n) for(ll i = 0; i < (n); i++)
#define REP2(i,a,b) for(ll i = (a); i < (b); i++)
#define REP3(i,a,b,c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overlord3(__VA_ARGS__,REP3,REP2,REP1)(__VA_ARGS__)
#define PER1(i,n) for(ll i = (n)-1; i >= 0; i--)
#define PER2(i,a,b) for(ll i = (a)-1; i >= b; i--)
#define PER3(i,a,b,c) for(ll i = (a)-1; i >= b; i -= c)
#define per(...) overlord3(__VA_ARGS__,PER3,PER2,PER1)(__VA_ARGS__)
#define fi first
#define se second
#define pb push_back
#define si(c) (int)(c).size()
#define all(c) c.begin(),c.end()
#define lb(c,x) distance((c).begin(),lower_bound(all(c),x))
#define ub(c,x) distance((c).begin(),upper_bound(all(c),x))
#define SORT(c) sort(all(c))
#define REV(c) reverse(all(c))
#define UNIQUE(c) SORT(c),c.erase(unique(all(c)),c.end())
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
vvc<int>road(N);
rep(i,M) {
road[A[i]].pb(B[i]);
road[B[i]].pb(A[i]);
}
vvc<int>ki1(N);
vvc<int>ki2(N);
{
vc<int>used(N);
auto dfs = [&](auto &dfs,int n) -> void {
used[n] = 1;
for(auto i:road[n]) {
if(!used[i]) {
ki1[n].pb(i);
ki2[n].pb(i);
ki2[i].pb(n);
dfs(dfs,i);
}
}
};
dfs(dfs,0);
}
vc<int>f(N);
{
auto dfs = [&](auto &dfs,int n) -> int {
int res = 1;
for(auto i:ki1[n]) {
res += dfs(dfs,i);
}
if(res >= 60) {
f[n] = 1;
return 0;
}
else {
return res;
}
};
dfs(dfs,0);
}
int now1 = P,now2 = V;
{
vc<int>dist(N,-1);
dist[P] = 0;
queue<int>que;
que.push(P);
while(!que.empty()) {
int x = que.front();
que.pop();
for(auto i:ki2[x]) {
if(dist[i] == -1) {
dist[i] = dist[x]+1;
que.push(i);
}
}
}
int mi = -1;
rep(i,N) {
if(f[i]) {
if(mi == -1) mi = i;
else if(dist[mi] > dist[i]) mi = i;
}
}
vc<int>res;
que.push(mi);
while(!que.empty()) {
int x = que.front();
que.pop();
res.pb(x);
for(auto i:ki2[x]) {
if(dist[i] == dist[x]-1) {
que.push(i);
break;
}
}
}
REV(res);
rep(i,1,si(res)) {
now1 = res[i];
now2 = Move(res[i]);
}
}
ll ans = now2;
int cnt = 0;
auto dfs = [&](auto &dfs,int n) -> void {
if(cnt == 60) return;
ans |= (1ll << cnt)*now2;
cnt++;
if(cnt == 60) return;
for(auto i:ki1[n]) {
if(f[i]) continue;
now1 = i;
now2 = Move(i);
dfs(dfs,i);
now1 = n;
now2 = Move(n);
}
};
dfs(dfs,now1);
return ans;
}
