#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>graf[250010];
long long preorder[250010], preit;
long long r[250010];
vector<long long>rozmiary;
void dfs(int x, int o){
preorder[x]=preit++;
for(auto j: graf[x])
if(j!=o){
dfs(j, x);
r[x]+=r[j]+1;
}
long long pom = *lower_bound(rozmiary.begin(), rozmiary.end(), r[x]) - r[x];
preit+=pom;
r[x]+=pom;
}
void Encode(int n, int A[], int B[])
{
rozmiary.push_back(0);
while(rozmiary.size()<=60){
rozmiary.push_back(max(rozmiary.back()+1, (long long)(2ll*rozmiary.back())));
}
int i;
for(i=0;i<n-1;i++){
graf[A[i]].push_back(B[i]);
graf[B[i]].push_back(A[i]);
}
dfs(0,-1);
// for(int i=0;i<n;i++)
// printf("%d: %d %d %d\n", i, preorder[i], r[i], int(lower_bound(rozmiary.begin(), rozmiary.end(), r[i])-rozmiary.begin()));
for (int i = 0; i < n; ++i) {
Code(i, (long long)preorder[i]*rozmiary.size()+(long long)(lower_bound(rozmiary.begin(), rozmiary.end(), r[i])-rozmiary.begin()));
}
}
#include "Device.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long>rozmiary1;
void InitDevice()
{
rozmiary1.push_back(0);
while(rozmiary1.size()<=60){
rozmiary1.push_back(max(rozmiary1.back()+1, (long long)(2ll*rozmiary1.back())));
}
}
int Answer(long long S, long long T)
{
long long X1 = S/rozmiary1.size(),X2 = rozmiary1[S%rozmiary1.size()];
long long Y1 = T/rozmiary1.size(),Y2 = rozmiary1[T%rozmiary1.size()];
// cerr<<X1<<" "<<X2<<" "<<Y1<<" "<<Y2<<" "<<S<<" "<<T<<"\n";
if(X1<=Y1 && X1+X2>=Y1)return 1;
if(Y1<=X1 && Y2+Y1>=X1)return 0;
return 2;
}
