#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define ppp pair<pii, pii>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
static const ll maxn = 1e4+5;
static vector<int> g[maxn], G[maxn]; // 0-base
static vector<pii> mxdep(maxn);
static vector<int> sz(maxn), dfsord(maxn);
static vector<bool> occ(maxn);
static void findtree(int u){
occ[u] = 1;
for (auto v:G[u]){
if (occ[v]) continue;
g[u].pb(v);
g[v].pb(u);
findtree(v);
}
}
static void findd(int u, int pre){
mxdep[u] = {0, -1};
sz[u] = 1;
for (auto v:g[u]){
if (v == pre) continue;
findd(v, u);
if (mxdep[v].f > mxdep[u].f){
mxdep[u].f = mxdep[v].f;
mxdep[u].s = v;
}
sz[u] += sz[v];
}
}
static void dfs(int u, int pre, int &pus, ll X){
dfsord[u] = pus++;
MessageBoard(u, ((X&(1ll<<(dfsord[u]%60))) > 0));
if (mxdep[u].s != -1) dfs(mxdep[u].s, u, pus, X);
for (auto v:g[u]){
if (v == pre || v == mxdep[u].s) continue;
dfs(v, u, pus, X);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
REP(i, M){
G[A[i]].pb(B[i]);
G[B[i]].pb(A[i]);
}
findtree(0);
findd(0, -1);
int pp = 0;
dfs(0, -1, pp, X);
}
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define ppp pair<pii, pii>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
static const ll maxn = 1e4+5;
static vector<int> g[maxn], G[maxn]; // 0-base
static vector<pii> mxdep(maxn);
static vector<int> sz(maxn), dfsord(maxn), par(maxn);
static vector<bool> occ(maxn);
static void findtree(int u){
occ[u] = 1;
for (auto v:G[u]){
if (occ[v]) continue;
g[u].pb(v);
g[v].pb(u);
findtree(v);
}
}
static void findd(int u, int pre){
par[u] = pre;
mxdep[u] = {0, -1};
sz[u] = 1;
for (auto v:g[u]){
if (v == pre) continue;
findd(v, u);
if (mxdep[v].f > mxdep[u].f){
mxdep[u].f = mxdep[v].f;
mxdep[u].s = v;
}
sz[u] += sz[v];
}
}
static void dfs(int u, int pre, int &pus){
dfsord[u] = pus++;
// MessageBoard(u, (X&(1ll<<(dfsord[u]%60))));
if (mxdep[u].s != -1) dfs(mxdep[u].s, u, pus);
for (auto v:g[u]){
if (v == pre || v == mxdep[u].s) continue;
dfs(v, u, pus);
}
}
static ll myX = 0;
static void runback(int u, int pre, int iord){
if (dfsord[u] - iord >= 60) return;
int ret = Move(u);
myX += (1ll<<(dfsord[u]%60))*ret;
for (auto v:g[u]){
if (v == pre) continue;
runback(v, u, iord);
}
Move(pre);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
REP(i, M){
G[A[i]].pb(B[i]);
G[B[i]].pb(A[i]);
}
findtree(0);
findd(0, -1);
int pp = 0;
dfs(0, -1, pp);
int cur = P, ret;
while (sz[cur] < 60){
cur = par[cur];
ret = Move(cur);
}
if (cur == P){
myX += (1ll<<(dfsord[cur]%60))*V;
}
else{
myX += (1ll<<(dfsord[cur]%60))*ret;
}
int iord = dfsord[cur];
while(cur != -1){
for (auto v:g[cur]){
if (v != par[cur] && v != mxdep[cur].s){
runback(v, cur, iord);
}
}
if (mxdep[cur].s != -1 && dfsord[mxdep[cur].s] - iord < 60){
cur = mxdep[cur].s;
ret += Move(cur);
myX += (1ll<<(dfsord[cur]%60))*ret;
}
else break;
}
return myX;
}
