#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
void encode(int n, int h, int m, int* a, int* b){
vector<int> g[n];
for (int i = 0; i < m; i++){
g[a[i]].pb(b[i]);
g[b[i]].pb(a[i]);
}
vector<int> p(n, -1); p[0] = 0;
queue<int> q; q.push(0);
while (!q.empty()){
int v = q.front(); q.pop();
for (int i: g[v]){
if (p[i] == -1){
p[i] = v;
q.push(i);
}
}
}
for (int i = 1; i < n; i++){
for (int j = 0; j < 10; j++){
encode_bit((p[i] >> j) & 1);
}
}
for (int i = 1; i < h; i++){
vector<int> dist(n, 1e9); dist[i] = 0;
q.push(i);
while (!q.empty()){
int v = q.front(); q.pop();
for (int u: g[v]){
if (dist[u] == 1e9){
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
for (int i = 1; i < n; i++){
int x = dist[i] - dist[p[i]]; x++;
encode_bit((x >> 0) & 1);
encode_bit((x >> 1) & 1);
}
}
}
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
void decode(int n, int h){
vector<int> p(n), g[n];
for (int i = 1; i < n; i++){
for (int j = 0; j < 10; j++){
bool x = decode_bit();
if (x){
p[i] += (1 << j);
}
}
}
for (int i = 1; i < n; i++){
g[p[i]].pb(i);
g[i].pb(p[i]);
}
vector<int> D(n);
function<void(int)> dfs = [&](int v){
if (v){
D[v] = D[p[v]] + 1;
}
for (int i: g[v]){
if (i != p[v]){
dfs(i);
}
}
};
dfs(0);
for (int i = 0; i < n; i++){
hops(0, i, D[i]);
}
for (int i = 1; i < h; i++){
vector<int> V(n);
for (int j = 1; j < n; j++){
for (int k = 0; k < 2; k++){
bool x = decode_bit();
if (x){
V[j] += (1 << k);
}
}
}
// d[x] = d[p[x]] + V[x] - 1
vector<int> d(n);
function<void(int, int)> fill = [&](int v, int pr){
for (int i: g[v]){
if (i == pr) continue;
if (i == p[v]){
d[i] = d[v] - V[v] + 1;
}
else {
assert(v == p[i]);
d[i] = d[v] + V[i] - 1;
}
fill(i, v);
}
};
fill(i, -1);
for (int j = 0; j < n; j++){
hops(i, j, d[j]);
}
}
}
