#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define all(x) x.begin(), x.end()
#define TASK "nonsense"
/// end of template ///
const int N = 1e4 + 10;
const int mb = 60;
const int root=1;
static vector<ii> edge[N];
static int n,m,mess[N];
static vector<int> adj[N];
static queue<int> q;
static struct Dsu
{
int n,par[N];
Dsu() {}
void init(int _n)
{
n=_n;
for(int i=0;i<n;++i) par[i]=i;
}
int get(int x)
{
if(x==par[x]) return x;
return par[x]=get(par[x]);
}
bool unite(int x, int y)
{
int s=get(x),t=get(y);
if(s==t) return 0;
par[s]=t;
return 1;
}
} dsu;
static void dfs(int u, int pa)
{
vector<ii> &owner=edge[pa];
vector<ii> &dog=edge[u];
int leaf,cmPos;
for(int tri=0;tri<mb-1;++tri) for(int ok=0;ok<2;++ok)
{
int ver=(ok==0?owner[tri].fi:owner[tri].se);
int cnt=0;
for(int i=0;i<mb-1;++i) cnt+=(owner[i].fi==ver)+(owner[i].se==ver);
if(cnt==1 && ver!=pa)
{
leaf=ver;
cmPos=tri;
}
}
mess[u]=mess[leaf];
for(int tri=0;tri<mb-1;++tri) if(tri!=cmPos)
{
dog.pb(owner[tri]);
}
dog.pb({pa,u});
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n=N;
m=M;
dsu.init(n);
for(int i=0;i<m;++i)
{
int u=A[i],v=B[i];
if(dsu.unite(u,v))
{
adj[u].pb(v);
adj[v].pb(u);
}
}
memset(mess,-1,sizeof(mess));
q.push(root);
int tg=0;
mess[root]=tg++;
vector<ii> cur;
while(tg<mb)
{
int u=q.front(); q.pop();
for(int v : adj[u]) if(mess[v]==-1 && tg<mb)
{
cur.pb({u,v});
q.push(v);
mess[v]=tg++;
}
}
for(int i=0;i<n;++i) if(mess[i]!=-1) edge[i]=cur;
for(int i=0;i<n;++i) if(mess[i]!=-1)
{
for(int v : adj[i]) if(mess[v]==-1) dfs(v,i);
}
for(int i=0;i<n;++i) MessageBoard(i,(X>>mess[i])&1);
}
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
//// int testcase=1;
// cin>>testcase;
// while (testcase--)
// solve();
// return 0;
//}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define all(x) x.begin(), x.end()
#define TASK "nonsense"
/// end of template ///
const int N = 1e4 + 10;
const int mb = 60;
const int root=1;
static vector<ii> edge[N];
static int n,m,mess[N];
static vector<int> adj[N];
static queue<int> q;
static struct Dsu
{
int n,par[N];
Dsu() {}
void init(int _n)
{
n=_n;
for(int i=0;i<n;++i) par[i]=i;
}
int get(int x)
{
if(x==par[x]) return x;
return par[x]=get(par[x]);
}
bool unite(int x, int y)
{
int s=get(x),t=get(y);
if(s==t) return 0;
par[s]=t;
return 1;
}
} dsu;
static void dfs(int u, int pa)
{
vector<ii> &owner=edge[pa];
vector<ii> &dog=edge[u];
int leaf=1,cmPos=-1;
for(int tri=0;tri<mb-1;++tri) for(int ok=0;ok<2;++ok)
{
int ver=(ok==0?owner[tri].fi:owner[tri].se);
int cnt=0;
for(int i=0;i<mb-1;++i) cnt+=(owner[i].fi==ver)+(owner[i].se==ver);
if(cnt==1 && ver!=pa)
{
leaf=ver;
cmPos=tri;
}
}
if(min(leaf,cmPos==-1)) return void(cout<<1/0);
mess[u]=mess[leaf];
for(int tri=0;tri<mb-1;++tri) if(tri!=cmPos)
{
dog.pb(owner[tri]);
}
dog.pb({pa,u});
}
static ll ans=0;
static void trace(int u, int pa)
{
for(int v : adj[u]) if(v!=pa)
{
ans|=(1LL<<mess[v])*Move(v);
trace(v,u);
ans|=(1LL<<mess[u])*Move(u);
}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
n=N;
m=M;
dsu.init(n);
for(int i=0;i<m;++i)
{
int u=A[i],v=B[i];
if(dsu.unite(u,v))
{
adj[u].pb(v);
adj[v].pb(u);
}
}
memset(mess,-1,sizeof(mess));
q.push(root);
int tg=0;
mess[root]=tg++;
vector<ii> cur;
while(tg<mb)
{
int u=q.front(); q.pop();
for(int v : adj[u]) if(mess[v]==-1 && tg<mb)
{
cur.pb({u,v});
q.push(v);
mess[v]=tg++;
}
}
for(int i=0;i<n;++i) if(mess[i]!=-1) edge[i]=cur;
for(int i=0;i<n;++i) if(mess[i]!=-1)
{
for(int v : adj[i]) if(mess[v]==-1) dfs(v,i);
}
for(int i=0;i<n;++i) vector<int>().swap(adj[i]);
for(ii cm : edge[P])
{
adj[cm.fi].pb(cm.se);
adj[cm.se].pb(cm.fi);
}
trace(P,-1);
return ans;
}
//int main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
// int testcase=1;
// cin>>testcase;
// while (testcase--)
// solve();
// return 0;
//}
