#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
const int maxN = 250000, K = 252, maxM = 1000000;
int nr = 0, l[250009], length[250009], a[50009], firstAfter[maxM];
long long partialS[250009];
vector < int > v[250009];
void initA ()
{
a[1] = 1;
for (int i=2; i<=K; i++)
{
a[i] = (int) ((double) a[i - 1] * 1.05);
if (a[i] <= a[i - 1]) a[i] = a[i - 1] + 1;
}
int j = 1;
for (int i=1; i<=a[K]; i++)
{
while (a[j] < i)
j ++;
firstAfter[i] = j;
}
}
void dfs (int nod, int tata)
{
l[nod] = ++nr;
for (auto it : v[nod])
if (it != tata)
dfs (it, nod);
int L = firstAfter[nr - l[nod] + 1];
nr = l[nod] + a[L] - 1;
length[nod] = L;
}
void Encode (int N, int A[], int B[])
{
for (int i=0; i<N - 1; i++)
v[A[i]].push_back (B[i]),
v[B[i]].push_back (A[i]);
initA ();
dfs (0, -1);
for (int i=0; i<N; i++)
Code(i, 1LL * length[i] * maxM + l[i]);
}
#include "Device.h"
#include<bits/stdc++.h>
using namespace std;
const int maxN = 250000, K = 252, maxM = 1000000;
static int a[50009];
void InitDevice()
{
a[1] = 1;
for (int i=2; i<=K; i++)
{
a[i] = (int) ((double) a[i - 1] * 1.05);
if (a[i] <= a[i - 1]) a[i] = a[i - 1] + 1;
}
}
void decode (long long X, int &i, int &j)
{
j = X / maxM, i = X % maxM;
j = a[j] + i - 1;
}
int Answer (long long S, long long T)
{
int lS, rS; decode (S, lS, rS);
int lT, rT; decode (T, lT, rT);
if (lT <= lS && rS <= rT) return 0;
if (lS <= lT && rT <= rS) return 1;
return 2;
}
