#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
#include "Encoder.h"
const int N=3e5+5;
vi E[N];
vi code[N];
pair<int, vi > dfs(int v, int p){
priority_queue<pair<int, vi>, vector<pair<int, vi>>, greater<pair<int, vi> > > Q;
for(int u:E[v]){
if(u!=p){
Q.push(dfs(u, v));
}
}
if(Q.size()==0){
return {0, {v}};
}
else if(Q.size()==1){
auto child=Q.top();
for(int i:child.nd){
code[i].push_back(0);
}
child.st++;
child.nd.pb(v);
return child;
}
else{
while(Q.size()>1){
auto child1=Q.top();
Q.pop();
auto child2=Q.top();
Q.pop();
for(int i:child1.nd)code[i].pb(0);
for(int i:child2.nd)code[i].pb(1);
for(int i:child1.nd)child2.nd.pb(i);
child2.st++;
Q.push(child2);
}
auto child=Q.top();
child.nd.pb(v);
return child;
}
}
void Encode(int n, int A[], int B[])
{
/*for (int i = 0; i < N; ++i) {
Code(i, 0LL);
}*/
for(int i=0; i<n-1; i++){
E[A[i]].pb(B[i]);
E[B[i]].pb(A[i]);
}
int len=dfs(0, -1).st;
deb(len);
int LEN=35;
assert(len<LEN);
for(int i=0; i<n; i++){
reverse(all(code[i]));
//deb(i, code[i]);
code[i].pb(0);
code[i].resize(LEN, 1);
ll code_num=0;
for(int j=0; j<LEN; j++){
code_num+=(ll(code[i][j])<<j);
}
//deb(i, code[i]);
Code(i, code_num);
}
}
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
#include "Device.h"
void InitDevice()
{
}
bool substring(vi A, vi B){
if(B.size()<A.size())return 0;
B.resize(A.size());
return (A==B);
}
int Answer(long long S, long long T)
{
int LEN=35;
vi codeS, codeT;
for(int j=0; j<LEN; j++){
codeS.pb((S>>j)&1);
codeT.pb((T>>j)&1);
}
while(codeS.back()==1)codeS.pop_back();
codeS.pop_back();
while(codeT.back()==1)codeT.pop_back();
codeT.pop_back();
//deb(codeS, codeT);
if(substring(codeT, codeS))return 0;
if(substring(codeS, codeT))return 1;
return 2;
}
