#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 250'000 + 5;
vector<int> ad[mxN];
int timer;
int in[mxN], sz[mxN], out[mxN];
void dfs(int u, int p) {
in[u] = ++timer;
sz[u] = 1;
for (int v : ad[u]) {
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
}
int val = 1, power = 0;
while (val < sz[u]) {
val = max(val + 1, (int) ceil((double) 1.05 * val));
power++;
}
timer += val - sz[u];
sz[u] = val;
out[u] = power;
}
void Encode(int N, int A[], int B[]) {
for (int i = 0; i < N - 1; i++) {
ad[A[i]].push_back(B[i]);
ad[B[i]].push_back(A[i]);
}
dfs(0, -1);
for (int i = 0; i < N; ++i) {
Code(i, in[i] * 256 + out[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice() {
}
int get(int x) {
int val = 1;
for (int i = 0; i < x; i++) val = max(val + 1, (int) ceil((double) 1.05 * val));
return val;
}
int Answer(long long S, long long T) {
int inS = S / 256, inT = T / 256;
int outS = inS + get(S % 256), outT = inT + get(T % 256);
if (inT <= inS && outT >= outS) return 0;
if (inS <= inT && outS >= outT) return 1;
return 2;
}
