#include "Joi.h"
#include <bits/stdc++.h>
#define maxn 10005
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static int idx[maxn], pai[maxn], deep[maxn], cnt, maior;
static vector<int> grafo[maxn], tree[maxn];
void dfs(int x)
{
idx[x] = cnt++;
maior = max(maior, deep[x] + 1);
for(auto v: grafo[x])
{
if(idx[v] != -1) continue;
pai[v] = x;
deep[v] = deep[x] + 1;
tree[x].push_back(v);
tree[v].push_back(x);
dfs(v);
}
}
void Joi(int N, int M, int A[], int B[], ll X, int T)
{
memset(idx, -1, sizeof idx);
for(int i = 0; i < M; i++)
{
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
dfs(0);
for(int i = 0; i < N; i++)
{
int id = (idx[i] % 60);
if(X & (1LL<<id)) MessageBoard(i, 1);
else MessageBoard(i, 0);
}
}
#include "Ioi.h"
#include <bits/stdc++.h>
#define maxn 10005
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static int idx2[maxn], pai2[maxn], deep2[maxn], cnt2, maior2, dp[maxn];
static int opt[maxn];
static vector<int> grafo2[maxn], tree2[maxn];
static ll ans = 0;
static set<int> usados;
void dfs2(int x)
{
idx2[x] = cnt2++;
maior2 = max(maior2, deep2[x] + 1);
dp[x] = 0;
for(auto v: grafo2[x])
{
if(idx2[v] != -1) continue;
pai2[v] = x;
deep2[v] = deep2[x] + 1;
tree2[x].push_back(v);
tree2[v].push_back(x);
dfs2(v);
if(dp[v] + 1 > dp[x]) dp[x] = dp[v] + 1, opt[x] = v;
}
}
ll Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
memset(idx2, -1, sizeof idx2);
for(int i = 0; i < M; i++)
{
grafo2[A[i]].push_back(B[i]);
grafo2[B[i]].push_back(A[i]);
}
dfs2(0);
for(int i = 0; i < N; i++) deep2[i] = idx2[i]%60;
usados.insert(deep2[P] % 60);
if(V) ans += (1LL<< (deep2[P]%60) );
while(P != 0 and usados.size() < 60)
{
ll val = Move(pai2[P]), aux = deep2[pai2[P]]%60;
if(val && !usados.count(aux)) ans += (1LL<< (aux) );
usados.insert(aux);
P = pai2[P];
}
if(usados.size() >= 60) return ans;
while(usados.size() < 60 and opt[P])
{
ll val = Move(opt[P]), aux = deep2[opt[P]]%60;
if(val && !usados.count(aux)) ans += (1LL<< (aux) );
usados.insert(aux);
P = opt[P];
}
return ans;
}
