#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> adj[500000];
int pre[500000], len[500000], pw[300], cur;
const double r = 1.05;
void dfs(int x, int p) {
pre[x] = cur++;
for(int i : adj[x]) if(i != p) dfs(i, x);
int sz = cur-pre[x]+1;
len[x] = lower_bound(pw, pw+300, sz)-pw;
cur += pw[len[x]] - sz;
}
#undef int
void Encode(int N, int A[], int B[]) {
#define int long long
double num = 1;
pw[0] = 1;
for(int i = 1; i < 300; i++) {
num *= r;
pw[i] = (int)ceil(num);
}
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, len[i]+300*pre[i]);
#undef int
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int pw[300];
const double r = 1.05;
void InitDevice() {
double num = 1;
pw[0] = 1;
for(int i = 1; i < 300; i++) {
num *= r;
pw[i] = (int)ceil(num);
}
}
#undef int
int Answer(long long S, long long T) {
#define int long long
int pres = S/300, posts = pres+pw[S%300]-1;
int pret = T/300, postt = pret+pw[T%300]-1;
if(pres < pret && posts >= postt) return 1;
if(pret < pres && postt >= posts) return 0;
return 2;
#undef int
}
