#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>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);
}
vc<int>ok(N);
rep(i,N) {
if(!f[i]) continue;
vc<int>id;
auto dfs = [&](auto &dfs,int n) -> void {
id.pb(n);
for(auto i:ki1[n]) {
if(f[i]) continue;
dfs(dfs,i);
}
};
dfs(dfs,i);
rep(j,60) {
ok[id[j]] = 1;
}
}
vc<int>dist(N,-1),used(N);
queue<int>que;
rep(i,N) {
if(ok[i]) {
dist[i] = 0;
que.push(i);
}
}
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);
}
}
}
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:ki1[n]) {
if(f[i]) continue;
dfs(dfs,i);
}
};
dfs(dfs,i);
rep(j,60) {
used[id[j]] = 1;
col[id[j]] = 1 & (X >> j);
}
}
rep(i,N) {
if(!used[i]) {
col[i] = 1 & (X >> (60-dist[i]));
}
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]);
}
vc<int>pa(N);
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);
pa[i] = 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);
}
ll ans = 0;
int now1 = P,now2 = V;
int lim = 59;
{
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:ki1[n]) {
if(f[i]) continue;
dfs(dfs,i);
}
};
dfs(dfs,i);
rep(j,60) {
col[id[j]] = 1;
}
}
vc<int>dist(N,-1);
queue<int>que;
rep(i,N) {
if(col[i]) {
dist[i] = 0;
que.push(i);
}
}
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);
}
}
}
vc<int>res;
que.push(P);
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;
}
}
}
rep(i,si(res)) {
if(i) {
now1 = res[i];
now2 = Move(res[i]);
}
if(i+1 == si(res)) break;
ans |= (1ll << (61-si(res)+i))*now2;
lim--;
}
}
{
int now = now1;
while(!f[now]) {
now = pa[now];
}
vc<int>num(N,-1),used(N);
vc<int>id;
auto dfs = [&](auto &dfs,int n) -> void {
id.pb(n);
for(auto i:ki1[n]) {
if(f[i]) continue;
dfs(dfs,i);
}
};
dfs(dfs,now);
rep(j,60) {
num[id[j]] = j;
}
while(true) {
auto dfs2 = [&](auto &dfs2,int n) -> void {
used[n] = 1;
ans |= (1ll << num[n])*now2;
for(auto i:ki1[n]) {
if(num[i] == -1) continue;
if(num[i] > lim) continue;
if(used[i]) continue;
now1 = i;
now2 = Move(i);
dfs2(dfs2,i);
now1 = n;
now2 = Move(n);
}
};
dfs2(dfs2,now1);
if(now1 == now) break;
now1 = pa[now1];
now2 = Move(now1);
}
}
return ans;
}
