#include "Joi.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#define X first
#define Y second
#define PB push_back
using namespace std;
const int N = 1e5 + 500;
int dep[N], ppar[N], tr[N], mks[N], par[N];
int tko[N], bit[N], cur = 0;
vector < int > v[N];
int pr(int x){
if(x == ppar[x]) return x;
return ppar[x] = pr(ppar[x]);
}
bool cmp(int x, int y){
return mks[x] > mks[y];
}
int dfs(int x, int lst){
mks[x] = dep[x]; par[x] = lst;
vector < int > vv;
for(int y : v[x]){
if(y == lst) continue;
vv.PB(y);
dep[y] = dep[x] + 1;
dfs(y, x);
mks[x] = max(mks[x], mks[y]);
}
sort(vv.begin(), vv.end(), cmp);
v[x] = vv;
return mks[x];
}
void dfs2(int x){
if(cur == 60) return;
tko[x] = cur++; bit[x] = 1;
//printf("tko[ %d ] = %d bit[ %d ] = %d\n", x, tko[x], x, bit[x]);
for(int y : v[x])
dfs2(y);
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
for(int i = 0;i < n;i++)
ppar[i] = i;
for(int i = 0;i < m;i++){
if(pr(A[i]) == pr(B[i]))
continue;
ppar[pr(A[i])] = pr(B[i]);
v[A[i]].PB(B[i]);
v[B[i]].PB(A[i]);
tr[i] = 1;
}
dfs(0, 0);
if(mks[0] >= 59){
//printf("Slucaj 1\n");
for(int i = 0;i < n;i++)
MessageBoard(i, !!(X & (1LL << (dep[i] % 60))));
return;
}
//printf("Slucaj 2\n");
dfs2(0);
for(int i = 0;i < n;i++)
MessageBoard(i, !!(X & (1LL << tko[i])));
}
#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1e5 + 500;
int dep2[N], ppar22[N], tr2[N], mks2[N], par2[N];
int tko2[N], bit2[N], cur2 = 0;
ll ans = 0;
vector < int > v2[N];
int pr2(int x){
if(x == ppar22[x]) return x;
return ppar22[x] = pr2(ppar22[x]);
}
bool cmp2(int x, int y){
return mks2[x] > mks2[y];
}
int dfs2(int x, int lst){
mks2[x] = dep2[x]; par2[x] = lst;
vector < int > v2v2;
for(int y : v2[x]){
if(y == lst) continue;
v2v2.PB(y);
dep2[y] = dep2[x] + 1;
dfs2(y, x);
mks2[x] = max(mks2[x], mks2[y]);
}
sort(v2v2.begin(), v2v2.end(), cmp2);
v2[x] = v2v2;
return mks2[x];
}
void dfs22(int x){
if(cur2 == 60) return;
tko2[x] = cur2++; bit2[x] = 1;
for(int y : v2[x])
dfs22(y);
}
int odg2 = -1;
void odg2ov2or(int x, bool nazad){
ans += (1LL << tko2[x]) * odg2;
reverse(v2[x].begin(), v2[x].end());
for(int y : v2[x]){
if(bit2[y]){
odg2 = Move(y);
odg2ov2or(y, nazad || (y != v2[x].back()));
if(y != v2[x].back() || nazad){
odg2 = Move(x);
}
}
}
reverse(v2[x].begin(), v2[x].end());
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
for(int i = 0;i < n;i++)
ppar22[i] = i;
for(int i = 0;i < m;i++){
if(pr2(A[i]) == pr2(B[i]))
continue;
ppar22[pr2(A[i])] = pr2(B[i]);
v2[A[i]].PB(B[i]);
v2[B[i]].PB(A[i]);
tr2[i] = 1;
}
dfs2(0, 0);
if(mks2[0] >= 59){
int lst = V;
//printf("P = %d mks2[ %d ] = %d\n", P, P, mks2[P]);
while(mks2[P] - dep2[P] < 59){
lst = Move(par2[P]);
P = par2[P];
}
for(int i = 0;i < 60;i++){
ans += (1LL << (dep2[P] % 60)) * lst;
if(i < 59){
lst = Move(v2[P][0]);
P = v2[P][0];
}
}
return ans;
}
dfs22(0);
odg2 = V;
while(P != 0){
odg2 = Move(par2[P]);
P = par2[P];
}
odg2ov2or(0, 0);
return ans;
}
