#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
long double R=1.05;
int counter=0;
vector<int> in, out, vect;
vector<vector<int> > graph;
void init(){
int c=1, loop=19;
while (loop){
int temp=c*R;
if (temp==c)++temp;
vect.pb(temp);
if (temp>250000)--loop;
c=temp;
--loop;
}
}
void dfs(int node, int p){
in[node]=counter++;
for (auto num:graph[node])if (num!=p)dfs(num, node);
out[node]=counter=in[node]+*lower_bound(vect.begin(), vect.end(), counter-in[node]);
}
void Encode(int n, int a[], int b[]){
in.resize(n);
out.resize(n);
graph.resize(n);
init();
for (int i=0; i<n-1; ++i){
graph[a[i]].pb(b[i]);
graph[b[i]].pb(a[i]);
}
dfs(0, -1);
for (int i=0; i<n; ++i)Code(i, in[i]*vect.size()+(lower_bound(vect.begin(), vect.end(), out[i]-in[i])-vect.begin()));
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
long double R=1.15;
vector<int> vect;
void init(){
int c=1, loop=100;
while (loop){
int temp=c*R;
if (temp==c)++temp;
vect.pb(temp);
c=temp;
--loop;
}
}
void InitDevice(){
init();
}
int Answer(long long s, long long t){
pii a=mp(s/vect.size(), s/vect.size()+s%vect.size()), b=mp(t/vect.size(), t/vect.size()+t%vect.size());
if (a.fi<=b.fi&&b.fi<=a.se)return 1;
else if (b.fi<=a.fi&&a.fi<=b.se)return 0;
return 2;
}
