#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
int dst[44][1010];
vector<int> g[1010];
int par[1010];
int vis[1010];
void dfs(int v = 1){
vis[v] = 1;
for(auto i : g[v]) if(!vis[i]){
par[i] = v; dfs(i);
}
}
void bfs(int st){
dst[st][st] = 0;
queue<int> q; q.push(st);
while(q.size()){
int now = q.front(); q.pop();
for(auto nxt : g[now]) if(dst[st][nxt] == -1){
dst[st][nxt] = dst[st][now] + 1;
q.push(nxt);
}
}
}
void encode(int N, int H, int M, int *v1, int *v2){
int n = N, m = M, h = H;
for(int i=0; i<m; i++){
int s = v1[i] + 1, e = v2[i] + 1;
g[s].push_back(e); g[e].push_back(s);
}
dfs();
for(int i=2; i<=n; i++){
for(int k=0; k<10; k++) encode_bit(!!(par[i] & (1 << k)));
}
memset(dst, -1, sizeof dst);
for(int i=1; i<=h; i++) bfs(i);
vector<int> v;
for(int i=1; i<=h; i++) for(int j=2; j<=n; j++){
int t = dst[i][j] - dst[i][par[j]];
if(t == 1) encode_bit(0), encode_bit(0);
else if(t == -1) encode_bit(1), encode_bit(1);
else encode_bit(1), encode_bit(0);
//v.push_back(dst[i][j] - dst[i][par[j]] + 1);
}
}
//g++ grader.h grader.cpp encoder.h encoder.cpp decoder.h decoder.cpp -o main -std=c++14
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
/*
dst[i][j] - dst[i][par[j]]
1 : 0
-1 : 11
0 : 10
*/
int p[1010];
int mm[44][1010];
int chk[1010];
int ans[44][1010];
void go(int hh, int v){
if(v == 1) return;
if(!chk[p[v]]) go(hh, p[v]);
ans[hh][v] = ans[hh][p[v]] + mm[hh][v];
chk[v] = 1;
}
void decode(int N, int H) {
int n = N, h = H;
for(int i=2; i<=n; i++){
for(int j=0; j<10; j++) p[i] += (decode_bit() << j);
}
for(int i=1; i<=h; i++) for(int j=2; j<=n; j++){
int a = decode_bit(); int b = decode_bit();
if(!a){ mm[i][j] = 1; continue; }
if(b) mm[i][j] = -1;
else mm[i][j] = 0;
}
for(int i=1; i<=h; i++){
memset(chk, 0, sizeof chk);
chk[1] = 1;
for(int j=2; j<=n; j++) go(i, j);
}
for(int i=1; i<=h; i++) for(int j=1; j<=n; j++) hops(i-1, j-1, ans[i][j] - ans[i][i]);
}
//g++ grader.h grader.cpp encoder.h encoder.cpp decoder.h decoder.cpp -o main -std=c++14
