#include<bits/stdc++.h>
#include "Joi.h"
using namespace std;
#define ll long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 1e4 + 20;
const int S = 60;
vector<int> RL_J(MX, -1);
int leader_J(int u)
{
if(RL_J[u] < 0)
return u;
else
return RL_J[u] = leader_J(RL_J[u]);
}
bool merge_J(int u, int v)
{
u = leader_J(u);
v = leader_J(v);
if(u == v)
return false;
if(RL_J[u] < RL_J[v])
swap(u, v);
RL_J[v]+=RL_J[u];
RL_J[u] = v;
return true;
}
vector<int> adj_J[MX];
vector<int> pa_J(MX);
vector<int> DEP_J(MX);
vector<int> SUB_J(MX);
in furthest_J(int u, int p, int lvl)
{
DEP_J[u] = lvl;
in d = {lvl, u};
pa_J[u] = p;
for(int v: adj_J[u])
{
if(v==p)
continue;
d = max(d, furthest_J(v, u, lvl+1));
}
//cout << "For u = " << d[0] << " " << d[1] << endl;
return d;
}
vector<int> flt_J;
vector<bool> hmm_J;
void pre_J(int u, int p, int vertex)
{
SUB_J[u] = 1;
if(u == vertex)
{
hmm_J[u] = 1;
return;
}
for(int v: adj_J[u])
{
if(v==p)
continue;
pre_J(v, u, vertex);
hmm_J[u] = hmm_J[u]|hmm_J[v];
SUB_J[u]+=SUB_J[v];
}
return;
}
vector<bool> cutted_J;
void cut_J(int u, int p, int &target)
{
if(target == 0)
return;
if((!hmm_J[u]) && (target >= SUB_J[u]))
{
target-=SUB_J[u];
cutted_J[u] = 1;
return;
}
for(int v: adj_J[u])
{
if(v == p)
continue;
cut_J(v, u, target);
}
return;
}
void order_J(int u, int p)
{
if(flt_J.size() < S)
flt_J.pb(u);
int x = -1;
for(int v: adj_J[u])
{
if(v == p)
continue;
if(hmm_J[v])
{
x = v;
continue;
}
if(cutted_J[v])
continue;
order_J(v, u);
}
if(x != -1)
order_J(x, u);
return;
}
void Joi(int N, int M, int A[], int B[], ll X, int T)
{
for(int i = 0; i < N; i++)
adj_J[i].clear();
for(int i = 0; i < M; i++)
{
if(merge_J(A[i], B[i]))
{
adj_J[A[i]].pb(B[i]);
adj_J[B[i]].pb(A[i]);
}
}
int f1 = furthest_J(0, -1, 0)[1];
auto [D, f2] = furthest_J(f1, -1, 0);
if(D >= (S-1))
{
for(int i = 0; i < N; i++)
MessageBoard(i, (X>>(DEP_J[i]%S))&1);
return;
}
vector<int> pth;
int GG = f2;
while(GG != -1)
{
pth.pb(GG);
GG = pa_J[GG];
}
reverse(pth.begin(), pth.end());
int root = pth[pth.size()/2];
hmm_J.assign(N, false);
pre_J(root, -1, f2);
cutted_J.assign(N, false);
int SSSSS = N-60;
cut_J(root, -1, SSSSS);
order_J(root, -1);
vector<int> send(N, 0);
for(int i = 0; i < S; i++)
send[flt_J[i]] = (X>>i)&1;
for(int i = 0; i < N; i++)
MessageBoard(i, send[i]);
return;
}
#include<bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define ll long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 1e4 + 20;
const int S = 60;
vector<int> RL_I(MX, -1);
int leader_I(int u)
{
if(RL_I[u] < 0)
return u;
else
return RL_I[u] = leader_I(RL_I[u]);
}
bool merge_I(int u, int v)
{
u = leader_I(u);
v = leader_I(v);
if(u == v)
return false;
if(RL_I[u] < RL_I[v])
swap(u, v);
RL_I[v]+=RL_I[u];
RL_I[u] = v;
return true;
}
vector<int> adj_I[MX];
vector<int> pa_I(MX);
vector<int> DEP_I(MX);
vector<int> SUB_I(MX);
in furthest_I(int u, int p, int lvl)
{
DEP_I[u] = lvl;
in d = {lvl, u};
pa_I[u] = p;
for(int v: adj_I[u])
{
if(v==p)
continue;
d = max(d, furthest_I(v, u, lvl+1));
}
//cout << "For u = " << d[0] << " " << d[1] << endl;
return d;
}
vector<int> flt_I;
vector<bool> hmm_I;
void pre_I(int u, int p, int vertex)
{
SUB_I[u] = 1;
pa_I[u] = p;
if(u == vertex)
{
hmm_I[u] = 1;
return;
}
for(int v: adj_I[u])
{
if(v==p)
continue;
pre_I(v, u, vertex);
hmm_I[u] = hmm_I[u]|hmm_I[v];
SUB_I[u]+=SUB_I[v];
}
return;
}
vector<bool> cutted_I;
void cut_I(int u, int p, int &target)
{
if(target == 0)
return;
if((!hmm_I[u]) && (target >= SUB_I[u]))
{
target-=SUB_I[u];
cutted_I[u] = 1;
return;
}
for(int v: adj_I[u])
{
if(v == p)
continue;
cut_I(v, u, target);
}
return;
}
void order_I(int u, int p, int s)
{
//cout << "Currently at = " << u << endl;
//cout << "Size = " << flt_I.size() << endl;
if(flt_I.size() < S)
flt_I.pb(s);
if(flt_I.size() == S)
return;
int x = -1;
for(int v: adj_I[u])
{
if(v == p)
continue;
if(hmm_I[v])
{
x = v;
continue;
}
if(cutted_I[v])
continue;
//cout << "Mroving to " << v << endl;
int TT = Move(v);
//cout << "no problem " << endl;
order_I(v, u, TT);
if(flt_I.size() == S)
return;
//cout << "Mroving to " << u << endl;
Move(u);
//cout << "no problem" << endl;
}
if(x != -1)
order_I(x, u, Move(x));
return;
}
long long Ioi(int N, int M, int A[], int B[], int p, int v, int T)
{
for(int i = 0; i < N; i++)
adj_I[i].clear();
for(int i = 0; i < M; i++)
{
if(merge_I(A[i], B[i]))
{
adj_I[A[i]].pb(B[i]);
adj_I[B[i]].pb(A[i]);
}
}
int f1 = furthest_I(0, -1, 0)[1];
auto [D, f2] = furthest_I(f1, -1, 0);
//cout << f1 << " " << f2 << " " << D << endl;
vector<int> pth;
int GG = f2;
while(GG != -1)
{
pth.pb(GG);
GG = pa_I[GG];
}
reverse(pth.begin(), pth.end());
/*for(int x: pth)
cout << x << " ";
cout << endl;*/
if(D >= (S-1))
{
int ans[S];
if(DEP_I[p] >= (S-1))
{
ans[(DEP_I[p]%S)] = v;
for(int i = 1; i < S; i++)
{
p = pa_I[p];
ans[(DEP_I[p]%S)] = Move(p);
}
}
else
{
int x = p;
if(x != f1)
{
//cout << "hi" << endl;
while(pa_I[x] != f1)
{
//cout << "Moved to pa_i[x] = " << pa_I[x] << endl;
Move(pa_I[x]);
x = pa_I[x];
}
ans[0] = Move(f1);
}
else
ans[0] = v;
for(int i = 1; i < S; i++)
ans[i] = Move(pth[i]);
}
ll ANS = 0;
for(int i = 0; i < S; i++)
{
if(ans[i])
ANS^=(1ll<<i);
}
return ANS;
}
int root = pth[pth.size()/2];
hmm_I.assign(N, false);
flt_I.clear();
pre_I(root, -1, f2);
cutted_I.assign(N, false);
int SSSSS = N-60;
cut_I(root, -1, SSSSS);
//cout << f1 << endl;
//cout << root << endl;
while(p != root)
{
p = pa_I[p];
//cout << "Moving to " << p << endl;
v = Move(p);
//cout << "No issue " << endl;
}
order_I(root, -1, v);
ll ANS = 0;
for(int i = 0; i < S; i++)
if(flt_I[i])
ANS^=(1ll<<i);
return ANS;
}
