#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
void Encode(int N, int A[], int B[])
{
vector<vector<int>> g(N);
for (int i = 0; i < N - 1; i++) {
g[A[i]].pb(B[i]);
g[B[i]].pb(A[i]);
}
vector<int> rnd_ups(1 << 8);
rnd_ups[0] = 1;
for (int i = 1; i < 1 << 8; i++) {
rnd_ups[i] = max(rnd_ups[i - 1] + 1, int(rnd_ups[i - 1] * 1.05));
}
vector<int> tin(N), X(N);
int T = 0;
auto dfs = [&](int v, int p, auto&&self) -> void {
tin[v] = T++;
for (int u : g[v]) {
if (u != p) {
self(u, v, self);
}
}
int L = -1, R = sz(rnd_ups);
while (R - L > 1) {
int M = (L + R) / 2;
if (rnd_ups[M] < T - tin[v]) L = M;
else R = M;
}
T = tin[v] + rnd_ups[R];
X[v] = R;
};
dfs(0, 0, dfs);
for (int i = 0; i < N; i++) Code(i, (tin[i] << 8) | X[i]);
}
#include "Device.h"
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> rnd_ups(1 << 8);
void InitDevice() {
rnd_ups[0] = 1;
for (int i = 1; i < 1 << 8; i++) {
rnd_ups[i] = max(rnd_ups[i - 1] + 1, int(rnd_ups[i - 1] * 1.05));
}
}
int Answer(long long S, long long T) {
if (S == T) return 2;
ll tin1 = S / (1 << 8), tin2 = T / (1 << 8), tout1 = tin1 + rnd_ups[S % (1 << 8)], tout2 = tin2 + rnd_ups[T % (1 << 8)];
if (tin1 <= tin2 && tout2 <= tout1) return 1;
if (tin2 <= tin1 && tout1 <= tout2) return 0;
return 2;
// if ((S&T) != std::min(S, T)) return 2;
// if (H1 < H2) return 1;
// return 0;
}
