#include "Joi.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
namespace joi
{
const int nx=1e4+5;
// void MessageBoard(int u, int v)
// {
// cout<<u<<' '<<v<<'\n';
// }
vector<int> adj[nx], ve[nx];
bitset<nx> ed[nx];
queue<int> f;
bool vis[nx];
int par[nx], deg[nx], id[nx];
void init(int n)
{
for(int i = 0; i < n; i++)
{
adj[i].clear();
ve[i].clear();
ed[i].reset();
while(f.size()) f.pop();
vis[i]=0;
id[i]=0;
par[i]=-1;
deg[i]=0;
}
}
int find(int u)
{
if(par[u]==-1) return u;
return par[u]=find(par[u]);
}
bool join(int u, int v)
{
u=find(u);
v=find(v);
if(u==v) return 0;
par[v]=u;
return 1;
}
void joi(int n, int m, int a[], int b[], ll x, int t)
{
for(int i = 0; i < m; i++)
{
if(join(a[i], b[i]))
{
ed[a[i]][b[i]]=ed[b[i]][a[i]]=1;
adj[a[i]].emplace_back(b[i]);
adj[b[i]].emplace_back(a[i]);
}
}
f.push(0);
vis[0]=1;
ve[0].emplace_back(0);
while(f.size())
{
int u=f.front();
f.pop();
for(int v:adj[u])
{
if(ve[0].size()==60) break;
if(!vis[v])
{
ve[0].emplace_back(v);
vis[v]=1;
f.push(v);
}
}
}
if(ve[0].size()!=60) while(1);
for(int i = 0; i < 60; i++)
{
id[ve[0][i]]=i;
if(ve[0][i]!=0) ve[ve[0][i]]=ve[0];
}
while(f.size()) f.pop();
for(int i = 0; i < n; i++)
vis[i]=0;
for(int i = 0; i < 60; i++)
vis[ve[0][i]]=1, f.push(ve[0][i]);
while(f.size())
{
int u=f.front();
f.pop();
for(int i = 0; i < 60; i++)
for(int j = i+1; j < 60; j++)
if(ed[ve[u][i]][ve[u][j]])
deg[ve[u][i]]++, deg[ve[u][j]]++;
int nxt=-1;
for(int i = 0; i < 60; i++)
if(deg[ve[u][i]]==1 && ve[u][i]!=u)
nxt=i;
if(nxt==-1) while(1);
for(int i = 0; i < 60; i++)
for(int j = i+1; j < 60; j++)
if(ed[ve[u][i]][ve[u][j]])
deg[ve[u][i]]++, deg[ve[u][j]]--;
for(int v:adj[u])
{
if(!vis[v])
{
vis[v]=1;
f.push(v);
ve[v]=ve[u];
ve[v][nxt]=v;
id[v]=nxt;
}
}
}
for(int i = 0; i < n; i++)
MessageBoard(i, x>>id[i]&1);
}
};
void Joi(int n, int m, int a[], int b[], ll x, int t)
{
joi::init(n);
joi::joi(n, m, a, b, x, t);
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// vector<int> l, r;
// for(int i = 0; i < 59; i++)
// l.emplace_back(i), r.emplace_back(i+1);
// Joi(60, 59, l, r, 123, 1);
// }
#include "Ioi.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e4+5;
namespace ioi
{
// int Move(int u)
// {
// return (123ll>>u&1);
// }
vector<int> adj[nx], ve[nx];
bitset<nx> ed[nx];
queue<int> f;
bool vis[nx], ok[nx];
int par[nx], deg[nx], res[60], id[nx];
void init(int n)
{
for(int i = 0; i < n; i++)
{
adj[i].clear();
ve[i].clear();
ed[i].reset();
while(f.size()) f.pop();
vis[i]=0;
id[i]=0;
par[i]=-1;
deg[i]=0;
ok[i]=0;
}
}
int find(int u)
{
if(par[u]==-1) return u;
return par[u]=find(par[u]);
}
bool join(int u, int v)
{
u=find(u);
v=find(v);
if(u==v) return 0;
par[v]=u;
return 1;
}
void dfs(int u, int val)
{
res[id[u]]=val;
vis[u]=1;
for(int v:adj[u])
if(!vis[v] && ok[v])
dfs(v, Move(v)), Move(u);
}
ll ioi(int n, int m, int a[], int b[], int p, int val, int t)
{
for(int i = 0; i < m; i++)
{
if(join(a[i], b[i]))
{
ed[a[i]][b[i]]=ed[b[i]][a[i]]=1;
adj[a[i]].emplace_back(b[i]);
adj[b[i]].emplace_back(a[i]);
}
}
f.push(0);
vis[0]=1;
ve[0].emplace_back(0);
while(f.size())
{
int u=f.front();
f.pop();
for(int v:adj[u])
{
if(ve[0].size()==60) break;
if(!vis[v])
{
ve[0].emplace_back(v);
vis[v]=1;
f.push(v);
}
}
}
if(ve[0].size()!=60) while(1);
for(int i = 0; i < 60; i++)
{
id[ve[0][i]]=i;
if(ve[0][i]!=0) ve[ve[0][i]]=ve[0];
}
while(f.size()) f.pop();
for(int i = 0; i < n; i++)
vis[i]=0;
for(int i = 0; i < 60; i++)
vis[ve[0][i]]=1, f.push(ve[0][i]);
while(f.size())
{
int u=f.front();
f.pop();
for(int i = 0; i < 60; i++)
for(int j = i+1; j < 60; j++)
if(ed[ve[u][i]][ve[u][j]])
deg[ve[u][i]]++, deg[ve[u][j]]++;
int nxt=-1;
for(int i = 0; i < 60; i++)
if(deg[ve[u][i]]==1 && ve[u][i]!=u)
nxt=i;
if(nxt==-1) while(1);
for(int i = 0; i < 60; i++)
for(int j = i+1; j < 60; j++)
if(ed[ve[u][i]][ve[u][j]])
deg[ve[u][i]]++, deg[ve[u][j]]--;
for(int v:adj[u])
{
if(!vis[v])
{
vis[v]=1;
f.push(v);
ve[v]=ve[u];
ve[v][nxt]=v;
id[v]=nxt;
}
}
}
for(int u:ve[p]) ok[u]=1, vis[u]=0;
dfs(p, val);
ll ans=0;
for(int i = 0; i < 60; i++)
if(res[i]) ans|=(1ll<<i);
return ans;
}
};
ll Ioi(int n, int m, int a[], int b[], int p, int val, int t)
{
ioi::init(n);
return ioi::ioi(n, m, a, b, p, val, t);
}
// int main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// vector<int> l, r;
// for(int i = 0; i < 59; i++)
// l.emplace_back(i), r.emplace_back(i+1);
// cout<<Ioi(60, 59, l, r, 5, 1, 1);
// }
