#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 500005;
vector<int> G[kMaxN];
int Left[kMaxN], Right[kMaxN];
int nodes;
int n;
int DFS(int node, int par) {
if (par != -1)
G[node].erase(find(G[node].begin(), G[node].end(), par));
priority_queue<pair<int, int>> Q;
for (auto vec : G[node]) {
int h = DFS(vec, node);
Q.emplace(-h, vec);
}
while (Q.size() > 2) {
auto a = Q.top(); Q.pop();
auto b = Q.top(); Q.pop();
++nodes;
Left[nodes] = a.second;
Right[nodes] = b.second;
Q.emplace(min(a.first, b.first) - 1, nodes);
}
if (Q.size() == 0) { Left[node] = Right[node] = -1; return 0; }
if (Q.size() == 1) { Left[node] = Q.top().second;
Right[node] = -1; return 1 - Q.top().first; }
if (Q.size() == 2) {
auto a = Q.top(); Q.pop();
auto b = Q.top(); Q.pop();
Left[node] = a.second;
Right[node] = b.second;
return 1 - min(a.first, b.first);
}
assert(false);
}
void CodeShit(int node, long long pref) {
if (node == -1) return;
if (node < n) {
Code(node, pref);
}
CodeShit(Left[node], 2 * pref);
CodeShit(Right[node], 2 * pref + 1);
}
void Encode(int n, int A[], int B[]) {
::n = n;
for (int i = 0; i < n - 1; ++i) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
nodes = n;
DFS(0, -1);
CodeShit(0, 1LL);
}
#include "Device.h"
void InitDevice() {
}
bool ANC(long long anc, long long node) {
while (node != anc) {
if (node == 0) return false;
node /= 2;
}
return true;
}
int Answer(long long S, long long T) {
if (ANC(S, T)) return 1;
if (ANC(T, S)) return 0;
return 2;
}
