#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 250'010;
vector<int> nums;
vector<int> g[N];
int tim=0;
int f[N], s[N];
void dfs(int at, int p) {
f[at] = tim;
for(int to:g[at]) {
if(to==p)continue;
dfs(to, at);
}
auto it = lower_bound(nums.begin(), nums.end(), tim-f[at]);
s[at] = it-nums.begin();
tim += (*it);
}
void Encode(int n, int A[], int B[])
{
long double d = 1.05;
long double val = d;
while(val <= 3*N) {
if(!nums.size() or nums.back()!=(int)val)
nums.push_back(val);
val*=d;
}
for(int i=0;i+1<n;i++) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs(0, -1);
for(int i = 0;i<n;i++) {
// cout << f[i] << " " << f[i]+nums[s[i]]-1 << "\n";
// cout << ((long long)s[i]*N*3 +f[i])/3*N << endl;
Code(i, (long long)(f[i])*N*3 + s[i]);
}
// cout << "A" << endl;
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 250'010;
vector<int> nms;
void InitDevice()
{
long double d = 1.05;
long double val = d;
while(val <= 3*N) {
if(!nms.size() or nms.back()!=(int)val)
nms.push_back(val);
val*=d;
}
}
int Answer(long long S, long long T)
{
// cout << nms.size() << " " << (S/(3*N)) << endl;
// cout << nms.size() << " " << (T/(3*N)) << endl;
int fs = S/(3*N);
int ss = fs+nms[S%(3*N)]-1;
int ft = T/(3*N);
int st = ft+nms[T%(3*N)]-1;
// cout << fs << " " << ss << endl;
// cout << ft << " " << st << endl;
// cout << endl;
if(fs <= ft and st <= ss)return 1;
if(ft <= fs and ss <= st)return 0;
return 2;
}
