#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define emb emplace_back
#define MAXN 250000
typedef pair<int,int> ii;
const int D=18,SEG=12;
int cnt,numNode,dp[2*MAXN+5];
vector<int> g[MAXN+5],gb[2*MAXN+5];
int L[2*MAXN+5],R[2*MAXN+5],num=-1;
void initBT(int x,int par){
for(int i=0;i<(int)g[x].size();i++){
if(g[x][i]==par){
g[x].erase(g[x].begin()+i);
break;
}
}
int cn=g[x].size();
if(cn>2){
vector<int> bt(2*cn);
int l=cn,r=2*cn;
for(int i=l;i<r;i++)
bt[i]=g[x][i-cn];
l>>=1;r>>=1;
while(l>0){
for(int i=r-1;i>=l;i--){
bt[i]=(i>1?cnt++:x);
gb[bt[i]].emb(bt[2*i]);
gb[bt[i]].emb(bt[2*i+1]);
}
l>>=1;r>>=1;
}
}
else{
for(auto i:g[x])
gb[x].emb(i);
}
for(auto i:g[x])
initBT(i,x);
}
void dfs(int x){
dp[x]=1;
for(auto i:gb[x]){
dfs(i);
dp[x]=max(dp[x],dp[i]+1);
}
}
void leaf(int x,int group,int p){
if(x>=numNode) return;
//~ cout << ":" sp x sp group sp p << "\n";
long long code=group+((long long)p<<SEG);
code=code<<1|1;
Code(x,code);
}
void node(int x,int h){
if(x>=numNode) return;
//~ cout << ":" sp x sp L[x] sp R[x] sp h << "\n";
long long code=R[x]+((long long)L[x]<<SEG)+((long long)h<<(2*SEG));
code=code<<1;
Code(x,code);
}
void calc(int x,int h,bool lf){
if(lf){
leaf(x,num,h);
int t=0;
for(auto i:gb[x]){
calc(i,h<<1|t,1);
t^=1;
}
}
else{
if(dp[x]<=D){
L[x]=R[x]=++num;h=1;
leaf(x,num,h);
int t=0;
for(auto i:gb[x]){
calc(i,h<<1|t,1);
t^=1;
}
}
else{
L[x]=cnt;R[x]=0;
for(auto i:gb[x]){
if(gb[x].size()==1)
calc(i,h+1,0);
else calc(i,0,0);
L[x]=min(L[x],L[i]);
R[x]=max(R[x],R[i]);
}
node(x,h);
}
}
}
void Encode(int N, int A[], int B[])
{
for(int i=0;i<N-1;i++){
g[A[i]].emb(B[i]);
g[B[i]].emb(A[i]);
}
cnt=numNode=N;
initBT(0,-1);
//~ for(int i=0;i<cnt;i++){
//~ cout << i << ": ";
//~ for(auto j:gb[i])
//~ cout << j << " ";
//~ cout << "\n";
//~ }
dfs(0);
calc(0,0,0);
}
#include "Device.h"
#include <bits/stdc++.h>
#define sp << " " <<
using namespace std;
const int seg=12;
void InitDevice(){}
int Answer(long long S, long long T){
if((S&1) && (T&1)){
S>>=1;T>>=1;
int path1=S>>seg;
int k1=S%(1<<seg);
int path2=T>>seg;
int k2=T%(1<<seg);
//~ cout << k1 sp path1 sp k2 sp path2 << "\n";
if(k1==k2){
auto ff=[](int x){
int ans=0;
while(x)
x>>=1,ans++;
return ans;
};
int len1=ff(path1);
int len2=ff(path2);
if(len1>len2)
swap(path1,path2);
for(int i=abs(len2-len1);i;i--)
path2>>=1;
if(path1==path2)
return (len1<len2?1:0);
return 2;
}
return 2;
}
else if(!(S&1) && (T&1)){
S>>=1;T>>=1;
int r=S%(1<<seg);
int l=(S>>seg)%(1<<seg);
int k=T%(1<<seg);
if(l<=k && k<=r)
return 1;
return 2;
}
else if((S&1) && !(T&1)){
S>>=1;T>>=1;
int r=T%(1<<seg);
int l=(T>>seg)%(1<<seg);
int k=S%(1<<seg);
if(l<=k && k<=r)
return 0;
return 2;
}
else{
S>>=1;T>>=1;
int r1=S%(1<<seg);
int l1=(S>>seg)%(1<<seg);
int h1=S>>(2*seg);
int r2=T%(1<<seg);
int l2=(T>>seg)%(1<<seg);
int h2=T>>(2*seg);
if(r1<l2 || r2<l1)
return 2;
if(l1==l2 && r1==r2)
return (h1<h2?1:0);
else{
int len1=r1-l1,len2=r2-l2;
return (len1>len2?1:0);
}
}
}
