#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7;
static int dsu[mxN], h[mxN];
static bool vis[mxN];
static vector<int> w[mxN], vc[mxN], Board[mxN];
static int Find(int j)
{
if (dsu[j] == j)
return j;
else
return dsu[j] = Find(dsu[j]);
}
static bool Union(int u, int v)
{
u = Find(u);
v = Find(v);
if (u == v)
return 0;
dsu[v] = u;
return 1;
}
static void Merge(int u, int v)
{
if (vc[u].size() > vc[v].size())
swap(vc[u], vc[v]);
for (int i : vc[u])
vc[v].push_back(i);
vc[u].clear();
}
static int lst = -1;
static void DFS(int j)
{
vc[j].push_back(j);
for (int i : w[j])
{
if (vc[i].size())
continue;
DFS(i);
if (lst != i)
Merge(i, j);
}
if (vc[j].size() >= 60)
lst = j;
}
static void Prepare(int j, int id, int tmp)
{
h[j] = tmp;
for (int i : w[j])
{
if (!vis[i] || h[i])
continue;
Prepare(i, id, tmp + 1);
h[j] = max(h[j], h[i]);
}
}
static bool cmp(int u, int v)
{
return h[u] > h[v] || (h[u] == h[v] && u > v);
}
static void Build(int j, int id)
{
if (Board[id].size() < 60)
Board[id].push_back(j);
else
MessageBoard(j, 0);
vis[j] = 0;
sort(w[j].begin(), w[j].end(), cmp);
for (int i : w[j])
{
if (!vis[i])
continue;
Build(i, id);
}
}
void Joi(int n, int m, int a[], int b[], long long x, int t)
{
for (int i = 0; i < n; i++)
dsu[i] = i;
for (int i = 0; i < m; i++)
{
if (Union(a[i], b[i]))
{
w[a[i]].push_back(b[i]);
w[b[i]].push_back(a[i]);
}
}
DFS(0);
if (lst)
Merge(0, lst);
for (int i = 0; i < n; i++)
{
if (vc[i].empty())
continue;
for (int j : vc[i])
vis[j] = 1;
Prepare(i, i, 1);
Build(i, i);
for (int j = 0; j < Board[i].size(); j++)
MessageBoard(Board[i][j], (x >> j) & 1);
}
}
#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7;
int dsu[mxN], h[mxN], trace[mxN], mn[mxN], vis[mxN];
bool bit[mxN];
vector<int> w[mxN], vc[mxN], Board;
int Find(int j)
{
if (dsu[j] == j)
return j;
else
return dsu[j] = Find(dsu[j]);
}
bool Union(int u, int v)
{
u = Find(u);
v = Find(v);
if (u == v)
return 0;
dsu[v] = u;
return 1;
}
void Merge(int u, int v)
{
if (vc[u].size() > vc[v].size())
swap(vc[u], vc[v]);
for (int i : vc[u])
vc[v].push_back(i);
vc[u].clear();
}
int lst = -1;
void DFS(int j)
{
vc[j].push_back(j);
for (int i : w[j])
{
if (vc[i].size())
continue;
DFS(i);
if (lst != i)
Merge(i, j);
}
if (vc[j].size() >= 60)
lst = j;
}
void Prepare(int j, int tmp)
{
h[j] = tmp;
vis[j]--;
for (int i : w[j])
{
if (vis[i] != 2)
continue;
Prepare(i, tmp + 1);
h[j] = max(h[j], h[i]);
}
}
static bool cmp(int u, int v)
{
return h[u] > h[v] || (h[u] == h[v] && u > v);
}
void Build(int j)
{
if (Board.size() < 60)
Board.push_back(j);
vis[j] = 0;
sort(w[j].begin(), w[j].end(), cmp);
for (int i : w[j])
{
if (!vis[i])
continue;
Build(i);
}
}
void BFS(int j)
{
queue<int> q;
q.push(j);
mn[j] = 0;
while (q.size())
{
int j = q.front();
q.pop();
for (int i : w[j])
{
if (mn[i] > mn[j] + 1)
{
mn[i] = mn[j] + 1;
q.push(i);
trace[i] = j;
}
}
}
}
int Walk(int j)
{
if (j == -1)
return -1;
if (Walk(trace[j]) >= 0)
return Move(j);
return 0;
}
bool cmpp(int u, int v)
{
return h[u] < h[v];
}
int cnt;
void Solve(int j)
{
sort(w[j].begin(), w[j].end(), cmpp);
cnt++;
vis[j] = 0;
for (int i : w[j])
{
if (!vis[i])
continue;
bit[i] = Move(i);
Solve(i);
if (cnt < 60)
Move(j);
}
}
ll Ioi(int n, int m, int a[], int b[], int stt, int v, int t)
{
for (int i = 0; i < n; i++)
dsu[i] = i;
for (int i = 0; i < m; i++)
{
if (Union(a[i], b[i]))
{
w[a[i]].push_back(b[i]);
w[b[i]].push_back(a[i]);
}
}
DFS(0);
if (lst)
Merge(0, lst);
int root = 0;
for (int i = 0; i < n; i++)
{
trace[i] = -1;
mn[i] = 1e9;
for (int j : vc[i])
{
if (j == stt)
root = i;
}
}
for (int i : vc[root])
vis[i] = 2;
Prepare(root, 1);
Build(root);
BFS(stt);
for (int i : Board)
{
vis[i] = 2;
if (mn[i] < mn[root])
root = i;
}
if (stt != root)
v = Walk(root);
bit[root] = v;
Prepare(root, 1);
Solve(root);
ll ans = 0;
for (int i = 0; i < 60; i++)
ans += (1LL * bit[Board[i]] << i);
return ans;
}
/*
*/
