#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
constexpr int N = 25e4;
vector<int> graf[N+9];
ll pre[N+9];
ll post[N+9];
int skok[N+9];
vector<pair<ll,int>> skoki;
ll tajm=1;
int n;
void dfs(int v, int par){
pre[v]=tajm++;
for (int x:graf[v]){
if (x!=par)dfs(x,v);
}
ll rozn=tajm-pre[v];
auto it = upper_bound(skoki.begin(),skoki.end(),make_pair(rozn,0));
tajm=pre[v]+(*it).first;
skok[v]=(*it).second;
post[v]=tajm;
}
void Encode(int n_, int A[], int B[]){
skoki.push_back({1,0});
for (int x=1;x<237;x++){
double duppa = (double) (skoki.back().first) * (double)1.05;
skoki.push_back({ceil(duppa),x});
}
n=n_;
for (int i = 1; i < n; ++i) {
graf[A[i-1]].push_back(B[i-1]);
graf[B[i-1]].push_back(A[i-1]);
}
dfs(0,-1);
for (ll x=0;x<n;x++){
//cerr << pre[x] << ' ' << post[x] << '\n';
Code(x,skoki.size()*pre[x]+skok[x]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<pair<ll,int>> skoki2;
void InitDevice(){
skoki2.push_back({1,0});
for (int x=1;x<237;x++){
double duppa = (double) (skoki2.back().first) * (double)1.05;
skoki2.push_back({ceil(duppa),x});
}
}
int Answer(long long S, long long T){
ll ps,ks,pt,kt;
ps = S/skoki2.size();
ks=ps+skoki2[S%skoki2.size()].first;
pt = T/skoki2.size();
kt=pt+skoki2[T%skoki2.size()].first;
if (ps<=pt && kt<=ks)return 1;
if (pt<=ps && ks<=kt)return 0;
return 2;
}
