#include "Joi.h"
#include "bits/stdc++.h"
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define dbg(x) "[" #x " = " << (x) << "]"
using namespace std;
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;
using vc = vector<char>;
struct DSU{
vector<int> lab;
DSU(int n) : lab(n, -1) {}
int root(int u){
return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}
bool join(int u, int v){
u = root(u);
v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
};
const int MAX = 1e4 + 5;
int N, depth[MAX], par[MAX], sub[MAX], c[MAX], mx[MAX], timer_dfs;
vi adj[MAX];
void dfs_len(int u, int p){
for(auto v : adj[u]) if(v != p){
depth[v] = depth[u] + 1;
dfs_len(v, u);
}
}
void dfs_sz(int u, int p){
sub[u] = 1;
for(auto v : adj[u]) if(v != p){
dfs_sz(v, u);
sub[u] += sub[v];
}
}
int find_centroid(int u, int p){
for(auto v : adj[u]) if(v != p && sub[v] * 2 > N){
return find_centroid(v, u);
}
return u;
}
tuple<int, int, int> find_diameter(){
depth[0] = 0;
dfs_len(0, -1);
int L1 = max_element(depth, depth + N) - depth;
depth[L1] = 0;
dfs_len(L1, -1);
int L2 = max_element(depth, depth + N) - depth;
return mt(L1, L2, depth[L2]);
}
void dfs_root(int u, ll X){
c[u] = (depth[u] % 60);
mx[u] = depth[u];
for(auto v : adj[u]){
adj[v].erase(find(all(adj[v]), u));
depth[v] = depth[u] + 1;
par[v] = u;
dfs_root(v, X);
maximize(mx[u], mx[v]);
}
}
void dfs_root2(int u){
mx[u] = depth[u];
for(auto v : adj[u]){
adj[v].erase(find(all(adj[v]), u));
depth[v] = depth[u] + 1;
par[v] = u;
dfs_root2(v);
maximize(mx[u], mx[v]);
}
}
void dfs_mark(int u, ll X){
if(timer_dfs == 60) return;
c[u] = (X >> (timer_dfs++) & 1);
for(auto v : adj[u]){
dfs_mark(v, X);
}
}
void add(int u, int pre, int& need, vi& vis){
if(!need) return;
vis.pb(u);
--need;
// cout << "ss : " << u << '\n';
for(auto v : adj[u]){
add(v, u, need, vis);
}
vis.pb(pre);
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
DSU dsu(N);
::N = N;
FOR(i, 0, M){
if(dsu.join(A[i], B[i])){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
}
int L1, L2, dist;
tie(L1, L2, dist) = find_diameter();
FOR(i, 0, N) c[i] = -1;
if(dist >= 59){
//root tree at L1
depth[L1] = 0;
dfs_root(L1, X);
} else{
dfs_sz(0, -1);
int centroid = find_centroid(0, -1);
depth[centroid] = 0;
dfs_root2(centroid);
// cout << dbg(centroid) << "JOI\n";
FOR(i, 0, N) sort(all(adj[i]), [&](int a, int b){ return mx[a] > mx[b]; });
int low = -1;
// FOR(i, 0, N) cout << depth[i] << " \n"[i == N-1];
FOR(i, 0, N) if(low == -1 || depth[low] < depth[i]) low = i;
// cout << dbg(low) << '\n';
vb one_time_called(N, false);
vector<vi> visits;
int u = low;
while(u != centroid){
one_time_called[u] = true;
visits.pb({u});
u = par[u];
}
one_time_called[centroid] = true;
visits.pb({centroid});
reverse(all(visits));
int need = 60 - sz(visits);
FOR(i, 0, sz(visits)){
int r = visits[i][0];
for(auto child : adj[r]){
if(!one_time_called[child]){
add(child, r, need, visits[i]);
}
}
}
// cout << '\n';
//
// cout << "tour JOI : ";
FOR(i, 0, sz(visits)){
for(auto j : visits[i]){
if(c[j] == -1) {
c[j] = timer_dfs++;
// cout << j << ' ';
}
}
}
// cout << '\n';
}
FOR(i, 0, N){
MessageBoard(i, (c[i] == -1 ? 0 : (X >> c[i] & 1)));
}
}
#include "Ioi.h"
#include "bits/stdc++.h"
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define dbg(x) "[" #x " = " << (x) << "]"
using namespace std;
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;
using vc = vector<char>;
struct DSU{
vector<int> lab;
DSU(int n) : lab(n, -1) {}
int root(int u){
return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}
bool join(int u, int v){
u = root(u);
v = root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
};
const int MAX = 1e4 + 5;
int _N, _depth[MAX], _par[MAX], _sub[MAX], _c[MAX], _mx[MAX], _timer_dfs;
vi _adj[MAX], _adj_general[MAX];
void _dfs_len(int u, int p){
for(auto v : _adj[u]) if(v != p){
_depth[v] = _depth[u] + 1;
_dfs_len(v, u);
}
}
void _dfs_sz(int u, int p){
_sub[u] = 1;
for(auto v : _adj[u]) if(v != p){
_dfs_sz(v, u);
_sub[u] += _sub[v];
}
}
int _find_centroid(int u, int p){
for(auto v : _adj[u]) if(v != p && _sub[v] * 2 > _N){
return _find_centroid(v, u);
}
return u;
}
tuple<int, int, int> _find_diameter(){
_depth[0] = 0;
_dfs_len(0, -1);
int L1 = max_element(_depth, _depth + _N) - _depth;
_depth[L1] = 0;
_dfs_len(L1, -1);
int L2 = max_element(_depth, _depth + _N) - _depth;
return mt(L1, L2, _depth[L2]);
}
void _dfs_root(int u){
_c[u] = (_depth[u] % 60);
_mx[u] = _depth[u];
for(auto v : _adj[u]){
_adj[v].erase(find(all(_adj[v]), u));
_depth[v] = _depth[u] + 1;
_par[v] = u;
_dfs_root(v);
maximize(_mx[u], _mx[v]);
}
}
int MoveTo(int S, int SV, int T){
//return TV
if(S == T) return SV;
queue<int> q;
vi pre(_N, -1), d(_N, -1);
q.push(S);
d[S] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(auto v : _adj_general[u]){
if(d[v] == -1){
d[v] = d[u] + 1;
pre[v] = u;
q.push(v);
}
}
}
stack<int> st;
int u = T;
while(T != S){
assert(T != -1);
st.push(T);
T = pre[T];
}
int val = SV;
while(!st.empty()){
u = st.top(); st.pop();
val = Move(u);
}
return val;
}
void _add(int u, int pre, int& need, vi& vis){
if(!need) return;
vis.pb(u);
--need;
// cout << "insert in : " << u << '\n';
for(auto v : _adj[u]){
_add(v, u, need, vis);
}
// cout << "insert out : " << pre << '\n';
vis.pb(pre);
}
long long Ioi(int _N, int M, int A[], int B[], int P, int V, int T) {
DSU dsu(_N);
::_N = _N;
FOR(i, 0, M){
if(dsu.join(A[i], B[i])){
_adj[A[i]].pb(B[i]);
_adj[B[i]].pb(A[i]);
}
_adj_general[A[i]].pb(B[i]);
_adj_general[B[i]].pb(A[i]);
}
int L1, L2, dist;
tie(L1, L2, dist) = _find_diameter();
ll X = 0;
if(dist >= 59){
//root tree at L1
_depth[L1] = 0;
_dfs_root(L1);
FOR(i, 0, _N) sort(all(_adj[i]), [&](int a, int b){ return _mx[a] > _mx[b]; });
if(_depth[P] >= 59){
// cout << "gttggt\n";
X |= (1LL << (_c[P])) * V;
FOR(i, 0, 59){
P = _par[P];
V = Move(P);
X |= (1LL << (_c[P])) * V;
}
} else{
// cout << "wtfafafasd\n";
while(P != L1){
P = _par[P];
V = Move(P);
}
X |= (1LL << (_c[P])) * V;
FOR(i, 0, 59){
int nxt = -1;
for(auto u : _adj[P]){
if(_mx[u] >= 59){
nxt = u;
break;
}
}
assert(nxt != -1);
P = nxt;
V = Move(P);
X |= (1LL << (_c[P])) * V;
}
}
} else{
_dfs_sz(0, -1);
int centroid = _find_centroid(0, -1);
// cout << "before : " << X << '\n';
// cout << dbg(centroid) << "IOI\n";
_depth[centroid] = 0;
_dfs_root(centroid);
FOR(i, 0, _N) sort(all(_adj[i]), [&](int a, int b){ return _mx[a] > _mx[b]; });
V = MoveTo(P, V, centroid);
int low = -1;
// FOR(i, 0, _N) cout << _depth[i] << " \n"[i == _N-1];
FOR(i, 0, _N) if(low == -1 || _depth[low] < _depth[i]) low = i;
// cout << dbg(low) << '\n';
vb one_time_called(_N, false);
vector<vi> visits;
int u = low;
while(u != centroid){
one_time_called[u] = true;
visits.pb({u});
u = _par[u];
}
one_time_called[centroid] = true;
visits.pb({centroid});
reverse(all(visits));
int need = 60 - sz(visits);
// cout << need << '\n';
FOR(i, 0, sz(visits)){
int r = visits[i][0];
for(auto child : _adj[r]){
if(!one_time_called[child]){
_add(child, r, need, visits[i]);
}
}
}
// cout << '\n';
// cout << "tour IOI : ";
vi tour;
FOR(i, 0, _N) _c[i] = -1;
// FOR(i, 0, _N) cout << _c[i] << ' '; cout << '\n';
FOR(i, 0, sz(visits)){
for(auto j : visits[i]){
// cout << j << ' ' << _c[j] << '\n';
if(_c[j] == -1) {
_c[j] = _timer_dfs++;
// cout << "!" << ' ';
}
tour.pb(j);
}
}
// cout << dbg(_timer_dfs) << '\n';
// assert(_timer_dfs == 60);
// cout << '\n';
// cout << X << '\n';
X |= (1LL << (_c[centroid])) * V;
// cout << X << '\n';
FOR(i, 1, sz(tour)){
V = Move(tour[i]);
X |= (1LL << (_c[tour[i]])) * V;
// cout << "bum : " << X << '\n';
}
}
return X;
}
