#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug2(){cerr<<"\n";}
template<typename H, typename... T>
void debug2(H h, T... t){
cerr<<h;
if(sizeof...(t))cerr<<", ";
debug2(t...);
}
#define deb(x) cerr<<#x<<" = ";debug2(x);
mt19937 rng2(chrono::high_resolution_clock().now().time_since_epoch().count());
const int NN2=1e4+5;
#include "Joi.h"
vector<int> bit2;
vi E2[NN2];
int reszta2;
int vis2[NN2], czy2[NN2], kol2[NN2];
vector<pii> todo2;
int ddfs2(int v){
int m=0;
vis2[v]=2;
for(int u:E2[v]){
if(czy2[u] && vis2[u]!=2){
m=max(m, ddfs2(u));
}
}
m++;
todo2.eb(-m, v);
return m;
}
vi ddfs(int v){
vi V;
vis2[v]=1;
for(int u:E2[v]){
if(!vis2[u]){
vi V2=ddfs(u);
for(int i:V2)V.pb(i);
}
}
czy2[v]=1;
V.pb(v);
if(v==0 || (reszta2-V.size()>=60 && V.size()>=60)){
for(int i:V)czy2[i]=1;
ddfs2(v);
sort(all(todo2));
for(int i=0; i<60; i++)kol2[todo2[i].nd]=i;
for(pii i:todo2)czy2[i.nd]=0, vis2[i.nd]=1;
V.clear();
reszta2-=todo2.size();
todo2.clear();
}
return V;
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
reszta2=n;
for(int i=0; i<m; i++){
E2[A[i]].pb(B[i]);
E2[B[i]].pb(A[i]);
}
for(int i=0; i<60; i++)bit2.pb(X&1), X/=2;
ddfs(0);
for(int i=0; i<n; i++){
MessageBoard(i, bit2[kol2[i]]);
}
}
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t))cerr<<", ";
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int NN=1e4+5, INF=1e9+5;
#include "Ioi.h"
int bit[60];
int reszta;
vi E[NN];
int vis[NN], czy[NN], kol[NN], par[NN];
vector<pii> todo;
int pp;
int dfs2(int v){
int m=0;
vis[v]=2;
for(int u:E[v]){
if(czy[u] && vis[u]!=2){
m=max(m, dfs2(u));
}
}
m++;
todo.eb(-m, v);
return m;
}
void move(int x){
int t=Move(x);
bit[kol[x]]=t;
}
void dfs3(int v){
deb(v, kol[v]);
vis[v]=2;
for(int u:E[v]){
if(vis[u]==3){
move(u);
dfs3(u);
move(v);
}
}
}
vector<int> dfs(int v){
vis[v]=1;
vi V;
for(int u:E[v]){
if(!vis[u]){
par[u]=v;
vi V2=dfs(u);
for(int i:V2)V.pb(i);
}
}
//deb(v, 1);
if(v==200){
deb();
deb();
deb();
}
V.pb(v);
if(v==0 || (reszta-V.size()>=60 && V.size()>=60)){
deb(v, V.size());
for(int i:V)czy[i]=1;
dfs2(v);
sort(all(todo));
for(pii &i:todo){
if(i.nd==200){
deb(i.st, i.nd, czy[200], pp)
}
}
for(int i=0; i<60; i++)kol[todo[i].nd]=i, vis[todo[i].nd]=3;
if(czy[pp]){
deb(5, v);
while(vis[pp]!=3){
deb(pp, par[pp]);
move(par[pp]), pp=par[pp];
}
deb(5);
dfs3(pp);
pp=1e4;
}
for(pii i:todo)czy[i.nd]=0, vis[i.nd]=1;
V.clear();
reszta-=todo.size();
todo.clear();
}
return V;
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
reszta=n;
for(int i=0; i<m; i++){
E[A[i]].pb(B[i]);
E[B[i]].pb(A[i]);
}
pp=P;
dfs(0);
bit[kol[P]]=V;
ll x=0;
for(int i=59; i>=0; i--)x=x+x+bit[i];
deb(x);
return x;
}
