#include "Joi.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long
#define pii pair<int,int>
const int MAXN = 1e4+10 ;
using namespace std ;
int val[MAXN] , sub[MAXN] ;
int ini[MAXN] , fim[MAXN] ;
int group[MAXN] , father[MAXN] ;
vector<int> adj[MAXN] ;
vector<int> tree[MAXN] ;
bool freq[65] ;
bool mark[MAXN] ;
void dfs1(int x)
{
sub[x] = 1 ;
for(auto e : adj[x] )
{
if( sub[e] > 0) continue ;
dfs1(e) ;
tree[x].push_back(e) ;
sub[x] += sub[e] ;
tree[e].push_back(x) ;
father[e] = x ;
}
}
int qtd ;
void dfs2(int x)
{
if(qtd <= 0) return ;
freq[ val[x] ] = true ;
qtd-- ;
for(auto e : tree[x] )
{
if(qtd <= 0) return ;
if( group[e] == group[x] && e != father[x] && !freq[ val[e] ] )
dfs2(e) ;
}
if(qtd <= 0) return ;
if(!freq[val[father[x]]])
dfs2(father[x]) ;
}
int isOn(int i, ll x ) { return ((1LL<<i)&x) != 0; }
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
for(int i = 0 ; i < N ; i++ ) val[i] = -1 ;
father[0] = -1 ;
for(int i= 0 ; i < M ; i++ )
{
adj[ A[i] ].push_back( B[i] ) ;
adj[ B[i] ].push_back( A[i] ) ;
}
dfs1(0) ;
vector<int> fila(1,0) ;
int ini = 0 ;
while( ini < sz(fila) )
{
int x = fila[ini++] ;
vector<int> miniFila(1,x) ;
int miniIni = 0 ;
if( sub[x] >= 60 )
{
while(miniIni < sz(miniFila) && miniIni < 60 )
{
int miniX = miniFila[miniIni] ;
val[ miniX ] = miniIni++ ;
group[miniX] = -(x+1) ;
for(auto e : tree[miniX] )
if(val[e] == -1)
miniFila.push_back(e) ;
}
for(int i = miniIni ; i < sz(miniFila) ; i++ )
fila.push_back(miniFila[i]) ;
}
else
{
qtd = 60 - sub[x] ;
for(int i = 0 ; i < 60 ; i++ ) freq[i] = false ;
dfs2( father[x] ) ;
while(miniIni < sz(miniFila))
{
int miniX = miniFila[miniIni++] ;
group[miniX] = x+1 ;
for(int i = 0 ; i < 60 ; i++ )
if(freq[i] == false )
{
freq[i] = true ;
val[ miniX ] = i ;
break ;
}
for(auto e : tree[miniX] )
if(val[e] == -1)
miniFila.push_back(e) ;
}
}
}
//for(int i = 0 ;i < N ; i++ ) cout << val[i] << endl ;
for(int i = 0 ; i < N ; i++ )
MessageBoard( i, isOn(val[i] , X) ) ;
}
#include "Ioi.h"
#include <bits/stdc++.h>
#define debug printf
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long
const int MAX = 1e4+10 ;
using namespace std ;
int valor[MAX] , subarvore[MAX ] ;
int pai[MAX] , grupo[MAX] ;
int achei[65] ;
bool frequencia[65] ;
bool vis[MAX] ;
vector<int> graph[MAX] , arvore[MAX] ;
void dfs11(int x)
{
subarvore[x] = 1 ;
for(auto e : graph[x] )
{
if( subarvore[e] > 0) continue ;
dfs11(e) ;
arvore[x].push_back(e) ;
subarvore[x] += subarvore[e] ;
arvore[e].push_back(x) ;
pai[e] = x ;
}
}
int quantidade ;
void dfs22(int x)
{
if(quantidade <= 0) return ;
frequencia[ valor[x] ] = true ;
quantidade-- ;
for(auto e : arvore[x] )
{
if(quantidade <= 0) return ;
if( grupo[e] == grupo[x] && e != pai[x] && !frequencia[valor[e]] )
dfs22(e) ;
}
if(quantidade <= 0) return ;
if(!frequencia[valor[pai[x]]])
dfs22(pai[x] ) ;
}
int qtdd = 60 ;
void dfsTraversal(int x)
{
if(qtdd <= 0 ) return ;
vis[x] = true ;
qtdd-- ;
for(auto e : arvore[x])
{
if(qtdd <= 0 ) return;
if(e == pai[x] || grupo[e] != grupo[x] || vis[e] ) continue ;
achei[ valor[e] ] = Move(e);
dfsTraversal(e) ;
}
if(x == 0 || qtdd <= 0 ) return ;
achei[ valor[ pai[x] ] ] = Move(pai[x]) ;
if(!vis[ pai[x] ])
dfsTraversal(pai[x]) ;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
for(int i = 0 ; i < N ; i++ ) valor[i] = -1 ;
pai[0] = -1 ;
for(int i= 0 ; i < M ; i++ )
{
graph[ A[i] ].push_back( B[i] ) ;
graph[ B[i] ].push_back( A[i] ) ;
}
dfs11(0) ;
vector<int> fila(1,0) ;
int ini = 0 ;
while( ini < sz(fila) )
{
int x = fila[ini++] ;
vector<int> miniFila(1,x) ;
int miniIni = 0 ;
if( subarvore[x] >= 60 )
{
while(miniIni < sz(miniFila) && miniIni < 60 )
{
int miniX = miniFila[miniIni] ;
valor[ miniX ] = miniIni++ ;
grupo[miniX] = -(x+1) ;
for(auto e : arvore[miniX] )
if(valor[e] == -1)
miniFila.push_back(e) ;
}
for(int i = miniIni ; i < sz(miniFila) ; i++ )
fila.push_back(miniFila[i]) ;
}
else
{
quantidade = 60 - subarvore[x] ;
for(int i = 0 ; i < 60 ; i++ ) frequencia[i] = false ;
dfs22( pai[x] );
while(miniIni < sz(miniFila))
{
int miniX = miniFila[miniIni++] ;
grupo[miniX] = x+1 ;
for(int i = 0 ; i < 60 ; i++ )
if(frequencia[i] == false )
{
frequencia[i] = true ;
valor[ miniX ] = i ;
break ;
}
for(auto e : arvore[miniX] )
if(valor[e] == -1)
miniFila.push_back(e) ;
}
}
}
achei[ valor[P] ] = V ;
for(int i = 0 ; i< N ; i++ ) vis[i] = false ;
dfsTraversal(P) ;
ll resp = 0LL ;
for(int i = 0 ;i < 60 ; i++ )
resp += (1LL<<i) * achei[i] ;
return resp ;
}
