#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
#define ll long long
using namespace std;
const int maxn = 1005, maxh = 40;
int dist[maxh][maxn];
queue <int> q;
vector <int> v[maxn];
int bio[maxn];
int par[maxn];
void rek(int x, int p){
bio[x] = 1;
par[x] = p;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(bio[x2]) continue;
rek(x2, x);
}
}
void encode(int n, int h, int p, int *a, int *b){
memset(dist, -1, sizeof dist);
for(int i = 0; i < p; i++){
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
for(int i = 0; i < h; i++){
dist[i][i] = 0;
q.push(i);
while(!q.empty()){
int x = q.front();
q.pop();
for(int j = 0; j < v[x].size(); j++){
int x2 = v[x][j];
if(dist[i][x2] == -1){
dist[i][x2] = dist[i][x] + 1;
q.push(x2);
}
}
}
}
for(int i = 0; i < h; i++){
for(int j = 9; j >= 0; j--){
if(dist[0][i] & (1 << j)) encode_bit(1);
else encode_bit(0);
}
}
rek(0, -1);
for(int i = 1; i < n; i++){
ll b3 = 0;
for(int j = 0; j < h; j++){
b3 *= 3;
if(dist[j][i] - dist[j][par[i]] == 1) b3 += 1;
else if(dist[j][i] - dist[j][par[i]] == -1) b3 += 2;
}
for(int j = 9; j >= 0; j--){
if(par[i] & (1 << j)) encode_bit(1);
else encode_bit(0);
}
for(int j = 57; j >= 0; j--){
if(b3 & (1LL << j)) encode_bit(1);
else encode_bit(0);
}
}
}
#include <bits/stdc++.h>
#define ll long long
#include "grader.h"
#include "decoder.h"
using namespace std;
const int maxn = 1005, maxh = 40;
int dist[maxh][maxn];
int d[maxn][maxh];
vector <int> v[maxn];
void rek(int x, int h){
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
for(int j = 0; j < h; j++){
dist[j][x2] = dist[j][x] + d[x2][j];
}
rek(x2, h);
}
}
void decode(int n, int h){
for(int i = 0; i < h; i++){
for(int j = 0; j < 10; j++){
dist[0][i] *= 2;
dist[0][i] += decode_bit();
}
}
for(int i = 1; i < n; i++){
int p = 0;
for(int j = 0; j < 10; j++){
p *= 2;
p += decode_bit();
}
v[p].push_back(i);
ll b3 = 0;
for(int j = 0; j < 58; j++){
b3 *= 2;
b3 += decode_bit();
}
for(int j = h - 1; j >= 0; j--){
int x = b3 % 3;
if(x == 1) d[i][j] = 1;
if(x == 2) d[i][j] = -1;
b3 /= 3;
}
}
rek(0, h);
for(int i = 0; i < h; i++){
for(int j = 0; j < n; j++){
hops(i, j, dist[i][j]);
}
}
}
