#include "grader.h"
#include "encoder.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
queue <ll> Q;
vector <ll> adj[1000];
vector <array<ll, 2>> E, V;
array<ll, 9> cnt;
bool B[9];
ll dist[1000], P[1000];
void bfs(ll x) {
Q.push(x);
for (int i=0; i<1000; ++i) dist[i] = 1e18, P[i] = -1;
dist[x] = 0;
while (!Q.empty()) {
auto u = Q.front();
Q.pop();
for (auto v : adj[u]) {
if (dist[v] == (ll)1e18) dist[v] = dist[u]+1, P[v] = u, Q.push(v);
}
}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
E.clear();
for (int i=0; i<nv; ++i) adj[i].clear();
for (int i=0; i<ne; ++i) {
adj[v1[i]].push_back(v2[i]);
adj[v2[i]].push_back(v1[i]);
}
bfs(0);
for (int i=1; i<nv; ++i) {
E.push_back({P[i], i});
for (int j=0; j<10; ++j) {
if (P[i] & (1LL<<j)) encode_bit(1);
else encode_bit(0);
}
}
if (nh == 1) return;
vector <ll> F;
for (int i=1; i<nh; ++i) {
bfs(i);
for (auto [u, v] : E) {
F.push_back(dist[u]-dist[v]);
}
}
if ((F.size() & 1)) F.push_back(0);
for (int i=0; i<F.size(); i+=2) {
ll u = (F[i]+1) * 3 + (F[i+1]+1);
++cnt[u];
}
for (int i=0; i<9; ++i) V.push_back({cnt[i], i});
sort(V.begin(), V.end());
if (V[0][1] > V[1][1]) swap(V[0], V[1]);
B[V[0][1]] = B[V[1][1]] = 1;
for (int i=0; i<9; ++i) encode_bit((ll)B[i]);
for (int i=0; i<F.size(); i+=2) {
ll u = (F[i]+1) * 3 + (F[i+1]+1);
ll v = 0;
if (u == V[0][1]) encode_bit(1), v = 6;
else if (u == V[1][1]) encode_bit(1), v = 7;
else {
if (u < V[0][1]) v = u;
else if (u < V[1][1]) v = u-1;
else v = u-2;
}
for (int j=2; j>=0; --j) {
if (v & (1LL<<j)) encode_bit(1);
else encode_bit(0);
}
}
}
#include "grader.h"
#include "decoder.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long
using namespace std;
vector <array<ll, 2>> e, adj2[1000];
vector <ll> U, X;
ll n, dist2[1000], W[1000];
void dfs(ll u, ll p) {
for (auto [v, w] : adj2[u]) {
if (v == p) continue;
if (dist2[v] == (ll)1e18) {
dist2[v] = dist2[u]+w;
dfs(v, u);
}
}
}
void solve(ll u) {
for (int i=0; i<1000; ++i) adj2[i].clear(), dist2[i] = (ll)1e18;
dist2[u] = 0;
for (int i=0; i<e.size(); ++i) {
adj2[e[i][0]].push_back({e[i][1], -W[i]});
adj2[e[i][1]].push_back({e[i][0], W[i]});
}
dfs(u, -1);
for (int i=0; i<n; ++i) {
hops(u, i, dist2[i]);
}
}
void b3(ll u) {
X.push_back((ll)(u/3)-1);
X.push_back((ll)(u%3)-1);
}
void decode(int nv, int nh) {
n = nv;
for (ll i=1; i<nv; ++i) {
W[i-1] = -1;
ll u = 0;
for (int j=0; j<10; ++j) {
u += decode_bit() * (1LL<<j);
}
e.push_back({u, i});
}
solve(0);
if (nh == 0) return;
for (int i=0; i<9; ++i) {
if (decode_bit() == 1) U.push_back(i);
}
for (int i=0; i<(nh-1)*(nv-1); i+=2) {
ll a = decode_bit(), b = decode_bit(), c = decode_bit();
if (a == 1 && b == 1 && c == 1) {
c = decode_bit();
if (!c) b3(U[0]);
else b3(U[1]);
}
else {
ll u = a*4+b*2+c;
if (u >= U[0]) ++u;
if (u >= U[1]) ++u;
b3(u);
}
}
int k = 0;
for (int i=1; i<nh; ++i) {
for (int j=0; j<nv-1; ++j) {
W[j] = X[k++];
}
solve(i);
}
}
