#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int maxn = 1e3+5;
int E[maxn][maxn];
int dist[maxn][maxn];
int vis[maxn];
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
memset(E, 0, sizeof(E));
memset(dist, 0, sizeof(dist));
memset(vis, 0, sizeof(vis));
for(int i = 0; i < ne; i++)E[v1[i]][v2[i]] = E[v2[i]][v1[i]] = 1;
for(int i = 0; i < nh; i++){
dist[i][i] = 0;
queue<int> q;
q.push(i);
while(!q.empty()){
auto x = q.front();
q.pop();
for(int j = 0; j < nv; j++){
if(!E[x][j] || dist[i][j] || j == i)continue;
dist[i][j] = dist[i][x] + 1;
q.push(j);
}
}
}
mt19937 rng(69420);
vector<int> vec(nh);
iota(vec.begin(), vec.end(), 0);
shuffle(vec.begin(), vec.end(), rng);
for(int i = 0; i < nh; i++){
vis[vec[i]] = 1;
for(int j = 0; j < nv; j++){
if(vis[j])continue;
int mx = nv-1;
for(int k = 0; k < i; k++){
mx = min(mx, dist[vec[k]][vec[i]] + dist[vec[k]][j]);
}
mx--;
int tmp = dist[vec[i]][j]-1;
while(mx){
encode_bit(tmp&1);
tmp>>=1;
mx>>=1;
}
}
}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
const int maxn = 1e3+5;
int dist[maxn][maxn];
int vis[maxn];
}
void decode(int nv, int nh) {
memset(vis, 0, sizeof(vis));
mt19937 rng(69420);
vector<int> vec(nh);
iota(vec.begin(), vec.end(), 0);
shuffle(vec.begin(), vec.end(), rng);
for(int i = 0; i < nh; i++){
vis[vec[i]] = 1;
for(int j = 0; j < nv; j++){
if(vis[j]){
hops(vec[i], j, dist[j][vec[i]]);
continue;
}
int mx = nv-1;
for(int k = 0; k < i; k++){
mx = min(mx, dist[vec[k]][vec[i]] + dist[vec[k]][j]);
}
mx--;
dist[vec[i]][j] = 0;
int crr = 0;
while(mx){
dist[vec[i]][j]|=decode_bit()<<(crr++);
mx>>=1;
}
dist[vec[i]][j]++;
hops(vec[i], j, dist[vec[i]][j]);
}
}
}
