#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
#include "Joi.h"
void Joi(int n,int m,int a[],int b[],ll res,int t){
vi dep(n);
vvi G(n);
vb done(n,false);
vi id(n,-1);
rep(i,m){
G[a[i]].pb(b[i]);
G[b[i]].pb(a[i]);
}
vvi g(n);vi par(n,-1);
ll cnt=0;
vb sp(n,false);set<ll> S;
function<void(ll)> dfs=[&](ll i){
if(cnt<60){
id[i]=cnt;
sp[i]=true;
S.insert(i);
cnt++;
}
done[i]=true;
for(ll x:G[i])if(!done[x]){
g[i].pb(x);par[x]=i;dfs(x);
}
};dfs(0);
vector<set<ll>> memo(n);
rep(i,n)if(sp[i])memo[i]=S;
function<void(ll)> dfs2=[&](ll i){
int prev=-1;
if(id[i]==-1){
S.insert(i);
sp[i]=true;
auto itr=S.begin();
while(true){
assert(itr!=S.end());
if(*itr==i){
itr++;continue;
}
ll jisuu=0;
if(par[*itr]!=-1&&sp[par[*itr]])jisuu++;
for(ll x:g[*itr]){
if(sp[x])jisuu++;
if(jisuu>1)break;
}
assert(jisuu);
if(jisuu==1){
id[i]=id[*itr];
prev=*itr;
sp[*itr]=false;
S.erase(itr);
break;
}
itr++;
}
memo[i]=S;
}
for(ll x:g[i])dfs2(x);
if(prev!=-1){
sp[i]=false;
S.erase(i);
S.insert(prev);
sp[prev]=true;
}
};dfs2(0);
rep(i,n){
set<ll> U;
auto itr=memo[i].begin();
assert(memo[i].size()==60);
rep(i,60){
U.insert(id[*itr]);
itr++;
}
assert(U.size()==60);
}
// outv(id);
rep(i,n)MessageBoard(i,res>>id[i]&1);
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<P> vp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
#include "Ioi.h"
ll Ioi(int n,int m,int a[],int b[],int p,int v,int t){
vi dep(n);
vvi G(n);
vb done(n,false);
vi id(n,-1);
rep(i,m){
G[a[i]].pb(b[i]);
G[b[i]].pb(a[i]);
}
vvi g(n);vi par(n,-1);
ll cnt=0;
vb sp(n,false);set<ll> S;
function<void(ll)> dfs=[&](ll i){
if(cnt<60){
id[i]=cnt;
sp[i]=true;
S.insert(i);
cnt++;
}
done[i]=true;
for(ll x:G[i])if(!done[x]){
g[i].pb(x);par[x]=i;dfs(x);
}
};dfs(0);
vector<set<ll>> memo(n);
rep(i,n)if(sp[i])memo[i]=S;
function<void(ll)> dfs2=[&](ll i){
int prev=-1;
if(id[i]==-1){
S.insert(i);
sp[i]=true;
auto itr=S.begin();
while(true){
assert(itr!=S.end());
if(*itr==i){
itr++;continue;
}
ll jisuu=0;
if(par[*itr]!=-1&&sp[par[*itr]])jisuu++;
for(ll x:g[*itr]){
if(sp[x])jisuu++;
if(jisuu>1)break;
}
assert(jisuu);
if(jisuu==1){
id[i]=id[*itr];
prev=*itr;
sp[*itr]=false;
S.erase(itr);
break;
}
itr++;
}
memo[i]=S;
}
for(ll x:g[i])dfs2(x);
if(prev!=-1){
sp[i]=false;
S.erase(i);
S.insert(prev);
sp[prev]=true;
}
};dfs2(0);
vb use(n,false);vi num(n);
auto itr=memo[p].begin();
rep(i,60){
use[*itr]=true;
itr++;
}
num[p]=v;
REP(i,1,n)g[i].pb(par[i]);
function<void(ll,ll)> slv=[&](ll i,ll prv){
for(ll x:g[i])if(x!=prv&&use[x]){
num[x]=Move(x);
slv(x,i);
Move(i);
}
};slv(p,-1);
ll ans=0;
rep(i,n)if(use[i])ans+=num[i]<<id[i];
return ans;
}
