#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
const long long MAXN=1009;
vector<int> edg[MAXN];
long long father[MAXN];
long long dist[MAXN];
long long code[MAXN];
long long vis[MAXN];
void pB(int n,int bits)
{
for(int i=0;i<bits;i++)encode_bit(bool(n&(1LL<<i)));
}
void dfs(int a)
{
vis[a]=1;
for(auto i:edg[a])
{
if(vis[i])continue;
father[i]=a;
dfs(i);
}
}
void bfs(int start)
{
memset(dist,-1,sizeof(dist));
dist[start]=0;
queue<int> q;
q.push(start);
while(!q.empty())
{
int curr=q.front();
q.pop();
for(auto i:edg[curr])
{
if(dist[i]!=-1)continue;
dist[i]=dist[curr]+1;
q.push(i);
}
}
}
void encode(int nv, int nh, int ne, int *v1, int *v2)
{
memset(father,-1,sizeof(father));
for(int i=0;i<ne;i++)
{
edg[v1[i]].push_back(v2[i]);
edg[v2[i]].push_back(v1[i]);
}
dfs(0);
for(int i=0;i<nh;i++)
{
bfs(i);
pB(dist[0],10);
for(int j=1;j<nv;j++)
{
code[j]=code[j]*3+dist[father[j]]-dist[j]+1;
}
}
for(int i=1;i<nv;i++)
{
pB(father[i],10);
pB(code[i],58);
}
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
const long long MAXN1=1009;
long long father1[MAXN1];
long long ans[MAXN1][40];
long long code1[MAXN1][40];
vector<bool> bt;
long long f(int n,int h)
{
if(n==0)return ans[n][h];
if(ans[n][h]!=-1)return ans[n][h];
return ans[n][h]=f(father1[n],h)-code1[n][h];
}
void decode(int nv, int nh)
{
for(int i=0;i<nh*10+(nv-1)*68;i++)bt.push_back(decode_bit());
memset(ans,-1,sizeof(ans));
for(int i=0;i<nh;i++)
{
for(int j=i*10;j<i*10+10;j++)
{
ans[0][i]+=(1LL<<(j-i*10))*bt[j];
}
++ans[0][i];
}
long long x;
for(int i=1;i<nv;i++)
{
x=0;
for(int j=nh*10+(i-1)*68;j<nh*10+(i-1)*68+10;j++)
{
father1[i]+=(1LL<<(j-(nh*10+(i-1)*68)))*bt[j];
}
for(int j=nh*10+(i-1)*68+10;j<nh*10+(i-1)*68+68;j++)
{
x+=(1LL<<(j-(nh*10+(i-1)*68+10)))*bt[j];
}
for(int j=nh-1;j>=0;j--)
{
code1[i][j]=x%3-1;
x/=3;
}
}
for(int i=0;i<nh;i++)
{
for(int j=0;j<nv;j++)
{
hops(i,j,f(j,i));
}
}
}
