#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define emb emplace_back
#define inf 1000000
#define MAXN 250000
typedef pair<int,int> ii;
const int D=11;
int cnt,dp[MAXN+5][D+1];
vector<int> g[MAXN+5],gb[2*MAXN+5];
int L[MAXN+5],R[MAXN+5],VAL[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){
for(auto i:gb[x])
dfs(i);
for(int i=0;i<=D;i++)
dp[x][i]=inf;
if(gb[x].empty())
dp[x][0]=dp[x][1]=1;
else if(gb[x].size()==1){
int child=gb[x][0];
for(int j=1;j<=D;j++){
dp[x][j]=dp[child][j-1]+(j==1);
dp[x][0]=min(dp[x][0],dp[x][j]);
}
}
else{
int c1=gb[x][0],c2=gb[x][1];
for(int i=0;i<=D;i++)
for(int j=0;j<=D;j++)
dp[x][max(i,j)+1]=min(dp[x][max(i,j)+1],dp[c1][i]+dp[c2][j]+1-(i>0)-(j>0));
for(int i=1;i<=D;i++)
dp[x][0]=min(dp[x][0],dp[x][i]);
}
}
void calc(int x,int k){
if(k==0){
for(k=1;k<=D && dp[x][k]!=dp[x][0];k++);
VAL[x]=1;
num++;
}
L[x]=num;
if(gb[x].empty());
else if(gb[x].size()==1){
int child=gb[x][0];
VAL[child]=VAL[x]<<1;
calc(child,k-1);
}
else{
int c1=gb[x][0],c2=gb[x][1];
VAL[c1]=VAL[x]<<1;
VAL[c2]=VAL[x]<<1|1;
int k1,k2,ff=0;
for(int i=0;i<=D && !ff;i++){
for(int j=0;j<=D && !ff;j++){
if(max(i,j)+1!=k) continue;
if(dp[c1][i]+dp[c2][j]+1-(i>0)-(j>0)==dp[x][k])
k1=i,k2=j,ff=1;
}
}
calc(c1,k1);calc(c2,k2);
}
R[x]=num;
}
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=N;
initBT(0,-1);
//~ for(int i=0;i<cnt;i++){
//~ cout << i << ": ";
//~ for(auto j:gb[i])
//~ cout << j << " ";
//~ cout << "\n";
//~ }
dfs(0);
//~ for(int i=0;i<cnt;i++){
//~ for(int j=0;j<=D;j++)
//~ cout << dp[i][j] << " ";
//~ cout << "\n";
//~ }
calc(0,0);
for(int i=0;i<N;i++){
//~ cout << L[i] sp R[i] sp VAL[i] << "\n";
long long code=VAL[i]+((long long)R[i]<<11)+((long long)L[i]<<23);
Code(i,code);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice(){}
int Answer(long long S, long long T){
int val1=S%(1LL<<11);
int r1=(S>>11)%(1LL<<12);
int l1=(S>>23);
int val2=T%(1LL<<11);
int r2=(T>>11)%(1LL<<12);
int l2=(T>>23);
if(l1==l2){
if(val1<val2){
while(val1<val2)
val2>>=1;
if(val1==val2)
return 1;
return 2;
}
else{
while(val2<val1)
val1>>=1;
if(val1==val2)
return 0;
return 2;
}
}
else{
if(l1<=l2 && r2<=r1) return 1;
if(l2<=l1 && r1<=r2) return 0;
return 2;
}
}
