#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
namespace {
void dec_to_bin(int x){
for(int i = 0; i < 10; i++){
encode_bit(x%2);
x/=2;
}
}
int n;
vector<vector<int>> v;
vector<bool> bl;
vector<int> p;
void dfs(int nd, int ss){
if(bl[nd]) return;
bl[nd] = 1;
for(int x: v[nd]) if(x != ss) dfs(x, nd);
p[nd] = ss;
}
vector<int> bfs(int s){
vector<int> dis(n, -1);
queue<int> Q;
dis[s] = 0;
Q.push(s);
while(!Q.empty()){
int nd = Q.front(); Q.pop();
for(int x: v[nd]) if(dis[x] == -1){
dis[x] = dis[nd]+1;
Q.push(x);
}
}
return dis;
}
}
void encode(int _n, int h, int m, int *A, int *B){
n = _n;
v.assign(n, {});
bl.assign(n, 0);
p.assign(n, -1);
for(int i = 0; i < m; i++){
v[A[i]].pb(B[i]);
v[B[i]].pb(A[i]);
}
dfs(0, -1);
for(int i = 1; i < n; i++) dec_to_bin(p[i]);
for(int i = 0; i < h; i++){
auto dis = bfs(i);
dec_to_bin(dis[0]);
for(int j = 1; j < n; j++){
if(dis[j] == dis[p[j]]) encode_bit(0), encode_bit(0);
else if(dis[j] == dis[p[j]]+1) encode_bit(1), encode_bit(0);
else encode_bit(0), encode_bit(1);
}
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
namespace {
int bin_to_dec(int L){
int x = 0;
for(int i = 0; i < L; i++) x+=decode_bit()*(1<<i);
return x;
}
vector<vector<int>> v;
vector<int> p;
vector<int> diff;
void dfs(int nd, int d, int H){
d+=diff[nd];
hops(H, nd, d);
for(int x: v[nd]) dfs(x, d, H);
}
}
void decode(int n, int h){
v.assign(n, {});
p.assign(n, -1);
for(int i = 1; i < n; i++){
p[i] = bin_to_dec(10);
v[p[i]].pb(i);
}
for(int i = 0; i < h; i++){
int D = bin_to_dec(10);
diff.assign(n, 0);
for(int j = 1; j < n; j++){
int c = bin_to_dec(2);
if(c == 1) diff[j] = 1;
else if(c == 2) diff[j] = -1;
else diff[j] = 0;
}
dfs(0, D, i);
}
}
