#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
namespace A
{
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 10'007;
const int K = 60;
bool vis[N], czy[N];
int sum[N];
int il[N];
vector<int> ed[N];
int wzo[K + 10];
int ans[N];
bool Cp(int a, int b)
{
return (il[a] > il[b]);
}
void DFSB(int v, int dd)
{
vis[v] = 1;
dd %= K;
if(dd == 0)
czy[v] = 1;
sum[v] = 1; il[v] = 1;
vector<int> nw;
sort(ed[v].begin(), ed[v].end());
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(vis[ed[v][i]]) continue;
DFSB(ed[v][i], dd + 1);
il[v] = max(il[v], ed[v][i] + 1);
sum[v] += sum[ed[v][i]];
if(!czy[ed[v][i]])
nw.pb(ed[v][i]);
}
sort(nw.begin(), nw.end(), Cp);
ed[v] = nw;
//cerr << "DFS1 " << v << " " << sum[v] << " " << K << "\n";
if(sum[v] < K && czy[v])
czy[v] = 0;
if(czy[v])
{
il[v] = 0;
sum[v] = 0;
}
}
void DFSS(int v, int &cnt)
{
//cerr << "DFS Set " << v << " " << cnt << "\n";
ans[v] = wzo[cnt]; ++cnt;
int beg = cnt;
if(cnt >= K) return;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(cnt < K)
DFSS(ed[v][i], cnt);
else if(il[ed[v][i]] >= K - beg)
{
int a = beg;
DFSS(ed[v][i], a);
}
}
}
}
void Joi(int _N, int _M, int A[], int B[], long long _X, int _T)
{
using namespace A;
int n = _N, m = _M;
for(int i = 0; i < m; ++i)
{
ed[A[i]].pb(B[i]);
ed[B[i]].pb(A[i]);
}
for(int i = 0; i < K; ++i)
wzo[i] = (bool)((1LL<<(ll)i) & _X);
DFSB(0, 0);
int cnt;
for(int i = 0; i < n; ++i)
{
if(!czy[i]) continue;
cnt = 0;
DFSS(i, cnt);
}
for(int i = 0; i < n; ++i)
MessageBoard(i, ans[i]);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
namespace B
{
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 10'007;
const int K = 60;
bool vis[N], czy[N];
int sum[N], oj[N];
int il[N];
vector<int> ed[N];
int val[N];
int pos[N];
ll answer = 0LL;
bool Cp(int a, int b)
{
return (il[a] > il[b]);
}
void DFSB(int v, int dd)
{
vis[v] = 1;
dd %= K;
if(dd == 0)
czy[v] = 1;
sum[v] = 1; il[v] = 1;
vector<int> nw;
sort(ed[v].begin(), ed[v].end());
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(vis[ed[v][i]]) continue;
oj[ed[v][i]] = v;
DFSB(ed[v][i], dd + 1);
il[v] = max(il[v], ed[v][i] + 1);
sum[v] += sum[ed[v][i]];
if(!czy[ed[v][i]])
nw.pb(ed[v][i]);
}
sort(nw.begin(), nw.end(), Cp);
ed[v] = nw;
if(sum[v] < K && czy[v])
czy[v] = 0;
if(czy[v])
{
il[v] = 0;
sum[v] = 0;
}
}
void DFS2(int v, int &cnt)
{
//cerr << "DFS2 Pos: " << v << " " << cnt << "\n";
pos[v] = cnt + 1;
if(cnt >= K) return;
++cnt;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
DFS2(ed[v][i], cnt);
if(cnt >= K) return;
}
}
void DFSA(int v, int a, bool r)
{
answer += (1LL<<((ll)pos[v] - 1LL)) * (ll)a;
for(int i = (int)ed[v].size() - 1; i >= 0; --i)
{
if(pos[ed[v][i]] > 0)
{
int dd = Move(ed[v][i]);
DFSA(ed[v][i], dd, ((i != 0) | r));
}
}
if(r)
{
Move(oj[v]);
}
}
}
long long Ioi(int _N, int _M, int A[], int B[], int P, int V, int T)
{
using namespace B;
//int n = _N;
int m = _M;
for(int i = 0; i < m; ++i)
{
ed[A[i]].pb(B[i]);
ed[B[i]].pb(A[i]);
}
DFSB(0, 0);
vector<int> pth;
val[P] = V;
while(!czy[P])
{
pth.pb(P);
val[oj[P]] = Move(oj[P]);
P = oj[P];
}
pth.pb(P);
reverse(pth.begin(), pth.end());
if((int)pth.size() >= K)
{
ll ans = 0LL;
for(int i = 0; i < K; ++i)
ans += (1LL<<(ll)i) * val[pth[i]];
return ans;
}
int cnt = 0;
DFS2(P, cnt);
DFSA(P, val[P], 0);
return answer;
}
