#include<bits/stdc++.h>
#include "Encoder.h"
#define ll long long
using namespace std;
namespace encode{
    const int M=250052;
    const double q=0.23;
    int n,cnt,ver[M<<1],nxt[M<<1],h[M],cntdfn,dfn[M],siz[M];
    int f[M];
    inline void init(){
        f[0]=1;
        for(int i=1;i<512;i++)f[i]=min(1<<20,(int)max(1.0,q*f[i-1])+f[i-1]);
    }
    inline void add_edge(int x,int y){cnt++;ver[cnt]=y;nxt[cnt]=h[x];h[x]=cnt;}
    inline void dfs(int x){
        dfn[x]=++cntdfn;
        siz[x]=1;
        for(int i=h[x];i;i=nxt[i]){
            int y=ver[i];
            if(!dfn[y]){
                dfs(y);
                siz[x]+=siz[y];
            }
        }
        int p=lower_bound(f,f+512,siz[x])-f;
        siz[x]=f[p];
        cntdfn=dfn[x]+siz[x]-1;
        Code(x,512ll*dfn[x]+p);
    }
}
void Encode(int N,int A[],int B[]){
    using namespace encode;
    n=N;
    init();
    for(int i=0;i<n-1;i++){
        add_edge(A[i],B[i]),add_edge(B[i],A[i]);
    }
    dfs(0);
}

#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
namespace device{
    const int M=250052;
    const double q=0.23;
    int f[M];
    inline void init(){
        f[0]=1;
        for(int i=1;i<512;i++)f[i]=min(1<<20,(int)max(1.0,q*f[i-1])+f[i-1]);
    }
}
void InitDevice(){
    using namespace device;
    init();
}
int Answer(long long S,long long T){
    using namespace device;
    int dfns=S>>9,sizs=f[S&511ll],dfnt=T>>9,sizt=f[T&511ll];
    if(dfnt<dfns&&dfns<dfnt+sizt)return 0;
    if(dfns<dfnt&&dfnt<dfns+sizs)return 1;
    return 2;
}