#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
static vector <int> ke[1000];
static int p[1000],vis[1000],d[1000];
static void dfs(int u){
vis[u]=1;
for (int v:ke[u])
if (!vis[v]){
p[v]=u;
dfs(v);
}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
for (int i=0;i<ne;i++){
ke[v1[i]].push_back(v2[i]);
ke[v2[i]].push_back(v1[i]);
}
dfs(0);
for (int i=1;i<nv;i++)
for (int j=9;j>=0;j--)
encode_bit((p[i]>>j)&1);
queue <int> q;
for (int i=0;i<nh;i++){
fill(d,d+nv,-1);
q.push(i);
d[i]=0;
while (!q.empty()){
int u=q.front();
q.pop();
for (int v:ke[u])
if (d[v]==-1){
d[v]=d[u]+1;
q.push(v);
}
}
for (int j=0;j*10<nv;j++){
int val=0;
for (int k=min(j*10+9,nv-1);k>=j*10;k--)
val=val*3+d[k]-d[p[k]]+1;
for (int j=15;j>=0;j--)
encode_bit((val>>j)&1);
}
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
static int p[1000],d[1000];
static vector <int> ke[1000];
static int get(int i){
int val=0;
while (i--)
val=val*2+decode_bit();
return val;
}
static void dfs(int u, int par, int hub, int dist){
hops(hub,u,dist);
for (int v:ke[u])
if (v!=par)
dfs(v,u,hub,dist+d[v]);
if (u&&p[u]!=par)
dfs(p[u],u,hub,dist-d[u]);
}
void decode(int nv, int nh){
for (int i=1;i<nv;i++){
p[i]=get(10);
ke[p[i]].push_back(i);
}
for (int i=0;i<nh;i++){
for (int j=0;j*10<nv;j++){
int val=get(16);
for (int k=j*10;k<min(j*10+10,nv);k++,val/=3)
d[k]=val%3-1;
}
dfs(i,i,i,0);
}
}
