#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define sth cout<<"line "<<__LINE__<<"\n"
namespace {
const ld r = 1.053;
vector<ll> v;
ll pre[250005], sub[250005], cnt;
vector<int> adj[250005];
void dfs(int x, int p) {
pre[x]=cnt++;
sub[x]=1;
for(auto i: adj[x]) if(i!=p) {dfs(i,x); sub[x] += sub[i];}
sub[x] = *lower_bound(v.begin(),v.end(),sub[x]);
cnt = pre[x] + sub[x];
}
}
void Encode(int N, int A[], int B[])
{
ld x = 1;
for(int i=0;i<267;i++) {
if(!v.size()||floor(x)!=v.back()) v.push_back(floor(x));
x *= r;
}
for(int i=0;i<N-1;i++) adj[A[i]].push_back(B[i]),adj[B[i]].push_back(A[i]);
dfs(0,-1);
for (int i = 0; i < N; ++i) {
Code(i, 267*pre[i]+lower_bound(v.begin(),v.end(),sub[i])-v.begin());
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define sth cout<<"line "<<__LINE__<<"\n"
namespace {
const ld r = 1.053;
vector<ll> v;
}
void InitDevice() {
ld x = 1;
for(int i=0;i<267;i++) {
if(!v.size()||floor(x)!=v.back()) v.push_back(floor(x));
x *= r;
}
}
int Answer(long long S, long long T) {
int sp = S / 267, ss = v[S % 267], tp = T / 267, ts = v[T % 267];
if(sp>=tp&&sp+ss<=tp+ts) return 0;
if(tp>=sp&&tp+ts<=sp+ss) return 1;
return 2;
}
