#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
#define maxn 250005
int pre[maxn],pst[maxn],cnt;
vector<int> seq,AL[maxn];
void build(){
const long double factor = 2;
seq.pb(0);seq.pb(1);
for(int i=2;i<256;++i){
int x=(int)(factor*seq.back());
if(x==seq.back())++x;
seq.pb(x);
}
}
void dfs(int u){
pre[u]=cnt++;
for(int v:AL[u]){
if(pre[v]==-1)dfs(v);
}
int pos=lower_bound(all(seq),cnt-pre[u])-seq.begin();
cnt+=seq[pos]+pre[u]-cnt;
pst[u]=cnt-1;
}
void Encode(int n,int a[],int b[]){
build();
memset(pre,-1,sizeof pre);
for(int i=0;i<n-1;++i){
AL[a[i]].pb(b[i]);
AL[b[i]].pb(a[i]);
}
dfs(0);
//for(int i=0;i<n;++i)pf("%d %d\n",pre[i],pst[i]);
for(int i=0;i<n;++i){
int dist=pst[i]-pre[i]+1;
int x=lower_bound(all(seq),dist)-seq.begin();
assert(x<sz(seq)&&seq[x]==dist);
Code(i,(1ll<<20)*x+pre[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
int ones=(1<<20)-1;
vector<int> seq2;
void build2(){
const long double factor = 2;
seq2.pb(0);seq2.pb(1);
for(int i=2;i<256;++i){
int x=(int)(factor*seq2.back());
if(x==seq2.back())++x;
seq2.pb(x);
}
}
void InitDevice(){
build2();
}
int Answer(ll S, ll T){
ll preS=S&ones,preT=T&ones;
ll distS=S>>20,distT=T>>20;
ll pstS=preS+seq2[distS]-1,pstT=preT+seq2[distT]-1;
//pf("S: %lld %lld %lld\n",preS,distS,pstS);
//pf("T: %lld %lld %lld\n",preT,distT,pstT);
if(preT<=preS&&preS<=pstT)return 0;
if(preS<=preT&&preT<=pstS)return 1;
return 2;
}
