#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
namespace{
int pos[200100];
int a[200100], cnt[200100];
vector<int> dq[200100], q[200100];
const int MAXK = 60;
void dfs0(int v){
pos[v] = 1;
for(int to: dq[v]){
if(pos[to]) continue;
q[v].pb(to);
q[to].pb(v);
dfs0(to);
}
}
// pii dfs1(int v, int p){
// pii h={1, v};
// for(int to: q[v]){
// if(p == to) continue;
// pii g=dfs1(to, v);
// h = max(h, {g.ff + 1, g.ss});
// }
// return h;
// }
set<pii> h;
int K = 0;
int P[200100];
void dfs1(int v, int p){
if(K < MAXK){
a[v] = K ++;
// if(h.find({a[p], p}) != h.end() and (p != 0 or (p == 0 and cnt[0] > 1))) h.erase(h.find({a[p], p}));
// h.insert({a[v], v});
if(p != -1) cnt[v] = 1;
if(p != -1) cnt[p] ++;
}
P[v] = p;
for(int to: q[v]){
if(p == to) continue;
dfs1(to, v);
}
}
void dfs2(int v, int p){
pii g={-1, -1};
// cout<<v<<'\n';
if(a[v] == -1){
auto it = h.begin();
if(it -> ss == p){
it++;
}
g = *it;
h.erase(it);
a[v] = g.ff;
cnt[v] = 1;
cnt[p] ++;
cnt[g.ss] = 0;
h.insert({a[v], v});
if(cnt[p] == 2 and h.find({a[p], p}) != h.end()) h.erase(h.find({a[p], p}));
cnt[P[g.ss]]--;
if(cnt[P[g.ss]] == 1) h.insert({a[P[g.ss]], P[g.ss]});
}
// cout<<"ok\n";
int dp = -1;
for(int to: q[v]){
if(to == p) continue;
// dp = P[v];
P[v] = to;
dfs2(to, v);
}
P[v] = p;
if(g.ff != -1){
cnt[v] = 0;
cnt[p] --;
cnt[P[g.ss]] ++;
cnt[g.ss] = 1;
// for(pii x:h) cout<<x.ff<<' '<<x.ss<<'\n';
h.erase(h.find({a[v], v}));
// cout<<"ok";
// cout<<"suka\n";
if(cnt[p] == 1) h.insert({a[p], p});
if(cnt[P[g.ss]] == 2 and h.find({a[P[g.ss]], P[g.ss]}) != h.end()) h.erase(h.find({a[P[g.ss]], P[g.ss]}));
h.insert(g);
}
// cout<<"ok"<<' '<<v<<'\n';
// cout<<"suka\n";
}
}
void Joi(int n, int m, int A[], int B[], long long X, int T){
for(int i=0; i<n; i++) a[i] = -1;
for(int i=0; i<m; i++){
int l = A[i], r = B[i];
dq[l].pb(r);
dq[r].pb(l);
}
dfs0(0);
// int f = (dfs1(0, -1)).ss;
// pii g = (dfs1(f, -1));
// int s = g.ss;
// if(g.ff < 60){
dfs1(0, -1);
for(int i=0; i<n; i++){
// cout<<i<<' '<<cnt[i]<<'\n';
if(a[i] != -1 and cnt[i] == 1) h.insert({a[i], i});
}
dfs2(0, -1);
for(int i=0; i<n; i++){
// cout<<a[i]<<' ';
MessageBoard(i, bool(X & (1ll << a[i])));
}
// for(int i=0; i<60; i++){
// MessageBoard(i, bool(X & (1ll << i)));
// }
// for(int i=60; i<n; i++){
// MessageBoard(i, 0);
// }
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
namespace{
int pos[200100];
int a[200100], cnt[200100];
vector<int> dq[200100], q[200100];
const int MAXK = 60;
void dfs0(int v){
pos[v] = 1;
for(int to: dq[v]){
if(pos[to]) continue;
q[v].pb(to);
q[to].pb(v);
dfs0(to);
}
}
// pii dfs1(int v, int p){
// pii h={1, v};
// for(int to: q[v]){
// if(p == to) continue;
// pii g=dfs1(to, v);
// h = max(h, {g.ff + 1, g.ss});
// }
// return h;
// }
set<pii> h;
int K = 0;
int P[200100];
void dfs1(int v, int p){
if(K < MAXK){
a[v] = K ++;
// if(h.find({a[p], p}) != h.end() and (p != 0 or (p == 0 and cnt[0] > 1))) h.erase(h.find({a[p], p}));
// h.insert({a[v], v});
if(p != -1) cnt[v] = 1;
if(p != -1) cnt[p] ++;
}
P[v] = p;
for(int to: q[v]){
if(p == to) continue;
dfs1(to, v);
}
}
void dfs2(int v, int p){
pii g={-1, -1};
// cout<<v<<'\n';
if(a[v] == -1){
auto it = h.begin();
if(it -> ss == p){
it++;
}
g = *it;
h.erase(it);
a[v] = g.ff;
cnt[v] = 1;
cnt[p] ++;
cnt[g.ss] = 0;
h.insert({a[v], v});
if(cnt[p] == 2 and h.find({a[p], p}) != h.end()) h.erase(h.find({a[p], p}));
cnt[P[g.ss]]--;
if(cnt[P[g.ss]] == 1) h.insert({a[P[g.ss]], P[g.ss]});
}
// cout<<"ok\n";
int dp = -1;
for(int to: q[v]){
if(to == p) continue;
// dp = P[v];
P[v] = to;
dfs2(to, v);
}
P[v] = p;
if(g.ff != -1){
cnt[v] = 0;
cnt[p] --;
cnt[P[g.ss]] ++;
cnt[g.ss] = 1;
// for(pii x:h) cout<<x.ff<<' '<<x.ss<<'\n';
h.erase(h.find({a[v], v}));
// cout<<"ok";
// cout<<"suka\n";
if(cnt[p] == 1) h.insert({a[p], p});
if(cnt[P[g.ss]] == 2 and h.find({a[P[g.ss]], P[g.ss]}) != h.end()) h.erase(h.find({a[P[g.ss]], P[g.ss]}));
h.insert(g);
}
// cout<<"ok"<<' '<<v<<'\n';
// cout<<"suka\n";
}
}
ll X;
int us[100];
void dfs4(int v, int p, int k){
X += (1ll << a[v]) * k;
us[a[v]] = 1;
for(int to: q[v]){
if(p == to) continue;
if(us[a[to]] == 1) continue;
dfs4(to, v, Move(to));
Move(v);
}
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
for(int i=0; i<n; i++) a[i] = -1;
for(int i=0; i<m; i++){
int l = A[i], r = B[i];
dq[l].pb(r);
dq[r].pb(l);
}
dfs0(0);
for(int i=0; i<60; i++) us[i] = 0;
// int f = (dfs1(0, -1)).ss;
// pii g = (dfs1(f, -1));
// int s = g.ss;
// if(g.ff < 60){
dfs1(0, -1);
for(int i=0; i<n; i++){
if(a[i] != -1 and cnt[i] == 1) h.insert({a[i], i});
}
dfs2(0, -1);
X = 0;
dfs4(P, -1, V);
return X;
}
