#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
const int MAXN = 1e3 + 10;
static int pai[MAXN];
static int dist[MAXN][MAXN], marc[MAXN][MAXN];
static vector<int> adj[MAXN];
void send_pai(int n){
for(int i=1; i<n; i++){
for(int j=0; j<10; j++){
if(pai[i] & (1 << j)){
encode_bit(1);
} else encode_bit(0);
}
}
}
void send_hub(int n, int h){
for(int i=1; i<n; i++){
if(dist[h][i] < dist[h][pai[i]]){
encode_bit(0);
encode_bit(1);
} else if(dist[h][i] == dist[h][pai[i]]){
encode_bit(0);
encode_bit(0);
} else{
encode_bit(1);
encode_bit(0);
}
}
}
void bfs(int h){
queue<int> q;
q.push(h);
dist[h][h] = 0;
marc[h][h] = 1;
pai[0] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v]){
if(!marc[h][u]){
dist[h][u] = dist[h][v] + 1;
marc[h][u] = 1;
if(h == 0) pai[u] = v;
q.push(u);
}
}
}
}
void encode(int n, int h, int p, int *a, int *b){
for(int i=0; i<n; i++) adj[i].clear();
for(int i=0; i<h; i++){
for(int j=0; j<n; j++){
marc[i][j] = 0;
}
}
for(int i=0; i<p; i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for(int i=0; i<h; i++) bfs(i);
for(int i=1; i<h; i++){
for(int j=0; j<10; j++){
if(dist[i][0] & (1 << j)){
encode_bit(1);
} else encode_bit(0);
}
}
send_pai(n);
for(int i=1; i<h; i++) send_hub(n, i);
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
const int MAXN = 1e3 + 10;
static int pai[MAXN];
static int dist[MAXN][MAXN], marc[MAXN][MAXN];
int dif[MAXN];
static vector<int> adj[MAXN];
void find_pai(int n){
for(int i=1; i<n; i++){
pai[i] = 0;
for(int j=0; j<10; j++){
pai[i] += decode_bit() * (1 << j);
}
}
}
void find_hub(int n, int h){
for(int i=1; i<n; i++){
int x = 2 * decode_bit();
x += decode_bit();
dif[i] = 0;
if(x == 1){
dif[i] = -1;
} else if(x == 2) dif[i] = 1;
}
queue<int> q;
q.push(0);
marc[h][0] = 1;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v]){
if(!marc[h][u]){
marc[h][u] = 1;
dist[h][u] = dist[h][v] + dif[u];
q.push(u);
}
}
}
}
void decode(int n, int h){
for(int i=1; i<h; i++){
for(int j=0; j<10; j++){
dist[i][0] += decode_bit() * (1 << j);
}
}
find_pai(n);
for(int i=0; i<h; i++){
for(int j=0; j<n; j++){
marc[i][j] = 0;
}
}
for(int i=0; i<n; i++) adj[i].clear();
for(int i=1; i<n; i++){
adj[pai[i]].push_back(i);
adj[i].push_back(pai[i]);
}
queue<int> q;
for(int i=0; i<n; i++) dif[i] = 1;
q.push(0);
marc[0][0] = 1;
dist[0][0] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : adj[v]){
if(!marc[0][u]){
marc[0][u] = 1;
dist[0][u] = dist[0][v] + dif[u];
q.push(u);
}
}
}
for(int i=1; i<h; i++) find_hub(n, i);
for(int i=0; i<h; i++){
for(int j=0; j<n; j++){
hops(i, j, dist[i][j]);
}
}
}
