#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define int long long
int idx, code[500000];
vector<int> adj[500000];
void solve(vector<int> &v, int p, int l, int r) {
if(l > r) return;
if(l == r) {
code[v[l]] = 2*code[p];
} else if(r-l == 1) {
code[v[l]] = 2*code[p];
code[v[r]] = 2*code[p]+1;
} else {
int m = (l+r)/2;
code[++idx] = 2*code[p];
solve(v, idx, l, m);
code[++idx] = 2*code[p]+1;
solve(v, idx, m+1, r);
}
}
void dfs(int x, int p) {
vector<int> v;
for(int i : adj[x]) if(i != p) v.push_back(i);
solve(v, x, 0, v.size()-1);
for(int i : adj[x]) if(i != p) dfs(i, x);
}
#undef int
void Encode(int N, int A[], int B[]) {
#define int long long
for(int i = 0; i < N-1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
code[0] = 1;
idx = N-1;
dfs(0, -1);
for(int i = 0; i < N; i++) Code(i, code[i]);
#undef int
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice() {
}
int Answer(long long S, long long T) {
#define int long long
int ss = 64-__builtin_clzll(S);
int st = 64-__builtin_clzll(T);
if(ss == st) {
return 2;
} else if(ss > st) {
S >>= (ss-st);
if(S == T) return 0;
else return 2;
} else {
T >>= (st-ss);
if(S == T) return 1;
else return 2;
}
#undef int
}
