#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;
const int mxN = 250001;
int N;
vector<int> al[mxN];
int bits[mxN], code[mxN];
void dfs(int u, int p) {
int nc = 0;
for (int& v : al[u]) if (v != p) {
++nc;
}
if (nc > 0) {
--nc;
int shift = 0;
while (nc) shift++, nc >>= 1;
shift = max(shift,1);
int i = 0;
for (int& v : al[u]) if (v != p) {
bits[v] = bits[u] + shift;
code[v] = (code[u]<<shift) | i;
//TRACE(u _ v _ i _ code[v] _ bits[v]);
dfs(v,u);
++i;
}
}
//TRACE(u _ nc _ bits[u] _ code[u]);
}
void Encode(int N, int A[], int B[])
{
FOR(i,0,N-2){
al[A[i]].push_back(B[i]);
al[B[i]].push_back(A[i]);
}
bits[0] = 0, code[0] = 0;
dfs(0,-1);
for (int i = 0; i < N; ++i) {
Code(i, (ll)bits[i] | ((ll)code[i]<<5));
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;
const int MN = 1e6+5;
const int mod = 1e9+7;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
int b1 = S&((1<<5)-1), b2 = T&((1<<5)-1);
if (b1 == b2) return 2;
if (b1 == 0) return 1;
if (b2 == 0) return 0;
S >>= 5;
T >>= 5;
if (b1 < b2) {
if (S == (T>>(b2-b1))) return 1;
return 2;
} else {
if ((S>>(b1-b2)) == T) return 0;
return 2;
}
return 0;
}
