//MRasol kheyri
//Iran -> Khorasan -> ferdows -> Baghestan
//15/2/1405
//vasate azmoonima...
#include<bits/stdc++.h>
#include "Alice.h"
using namespace std ;
typedef long long ll ;
#define el '\n'
const ll maxn = 1e6 + 100 ;
const ll prime = 67 ;
ll n = 5000 ;
ll par[maxn] ;
vector<pair<int,int>> Alice(){
srand(time(0)) ;
ll x = setN(n) ;
par[1] = 0 ;
for(ll i = 2 ; i < n ; i++){
ll bit = i%prime ;
ll b = ((i-1)/2) + 1 ;
if((x>>bit)&1){
par[i] = b + (rand()%(i-b)) ;
}
else{
par[i] = rand()%b ;
}
}
vector<pair<int,int>> edge ;
for(ll i = 1 ; i < n ; i++){
edge.push_back({par[i]+1,i+1}) ;
}
return edge ;
}
//MRasol kheyri
//Iran -> Khorasan -> ferdows -> Baghestan
//15/2/1405
//vasate azmoonima...
#include<bits/stdc++.h>
#include "Bob.h"
using namespace std ;
typedef long long ll ;
#define el '\n'
const ll maxn = 1e6 + 100 ;
const ll prime = 67 ;
ll n = 5000 ;
ll par[maxn] , ok[maxn] ;
ll Bob(vector<pair<int,int>> V){
fill(par,par+n,-1) ;
for(ll i = 0 ; i < V.size() ; i++){
ll u = min(V[i].first,V[i].second) , v = max(V[i].first,V[i].second) ;
u-- , v-- ;
par[v] = u ;
}
ll x = 0 ;
for(ll i = 2 ; i < n ; i++){
ll bit = i%prime ;
if(par[i] == -1 || ok[bit]){continue;}
ok[bit] = 1 ;
ll b = ((i-1)/2) + 1 ;
if(b <= par[i]){
x += 1<<bit ;
}
}
return x ;
}
