#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
static vector<int> adjlst[250100];
static long long int pre[250100];
static long long int post[250100];
static int cont = 0;
static vector<long long int> plow;
static void dfs(int i, int p){
pre[i] = cont;
cont++;
for(int j : adjlst[i]){
if(j == p) continue;
dfs(j,i);
}
post[i] = lower_bound(plow.begin(),plow.end(),cont - pre[i]) - plow.begin();
cont = post[i] + plow[pre[i]];
}
void Encode(int N, int A[], int B[]){
for(int i = 0; i < N - 1; ++i) {
adjlst[A[i]].push_back(B[i]);
adjlst[B[i]].push_back(A[i]);
}
plow = {1};
for(int i = 1; i < 400; i++){
plow.push_back(ceil(plow.back() * 1.05) + 0.1);
}
dfs(0,-1);
for(int i = 0; i < N; i++){
Code(i,(post[i]<<22)+pre[i]);
}
}
/*int main(){
plow = {1};
for(int i = 1; i < 400; i++){
plow.push_back(ceil(plow.back() * 1.05) + 0.1);
}
printf("%lld",plow[18]);
}*/
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
static vector<long long int> plow;
void InitDevice(){
plow = {1};
for(int i = 1; i < 400; i++){
plow.push_back(ceil(plow.back() * 1.05) + 0.1);
}
}
int Answer(long long S, long long T){
long long int s1 = S % (1LL<<22);
long long int e1 = plow[(S>>22)];
e1 += s1;
long long int s2 = T % (1LL<<22);
long long int e2 = plow[(T>>22)];
e2 += s2;
if(s1 <= s2 && e2 <= e1){
return 1;
}
if(s2 <= s1 && e1 <= e2){
return 0;
}
return 2;
}
