#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 1005;
vector < ll > v[N], g[N];
ll dist[40][N];
bool vis[N];
ll n, h;
ll par[N];
void dfs(ll s){
vis[s] = 1;
for(auto u : v[s]){
if(!vis[u]){
g[s].pb(u);
g[u].pb(s);
par[u] = s;
dfs(u);
}
}
return;
}
void bfs(int source){
for(ll i = 0; i < n; i++) dist[source][i] = -1;
dist[source][source] = 0;
queue < ll > q; q.push(source);
while(q.size()){
auto node = q.front(); q.pop();
for(auto u : v[node]){
if(dist[source][u] == -1){
dist[source][u] = dist[source][node] + 1;
q.push(u);
}
}
}
return;
}
vector < ll > mp = {-1, 0, 1};
vector < ll > cnt(3, 0);
int convert(int num){
for(int i = 0; i < 3; i++){
if(mp[i] == num) return i;
}
cout << "Something is Wrrong\n";
return 3;
}
int start = 0;
void magic(ll s, ll p){
for(auto u : g[s]){
if(u - p){
cnt[convert(dist[start][u] - dist[start][s])]++;
magic(u, s);
}
}
return;
}
void final(ll s, ll p){
for(auto u : g[s]){
if(u - p){
ll k = convert(dist[start][u] - dist[start][s]);
if(k == 0){
encode_bit(0);
}else{
encode_bit(1);
encode_bit(k - 1);
}
final(u, s);
}
}
return;
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
n = nv, h = nh;
memset(vis, 0, sizeof(vis));
for(ll i = 0; i < ne; i++){
int x = v1[i] , y = v2[i];
v[x].pb(y);
v[y].pb(x);
}
dfs(0);
for(ll i = 1; i < n; i++){
for(ll j = 0; j < 10; j++){
encode_bit((par[i] >> j)&1);
}
}
for(ll i = 0; i < n; i++){
sort(g[i].begin(), g[i].end());
}
for(ll i = 0; i < h; i++){
start = i;
bfs(i);
magic(i, -1);
}
if(cnt[0] >= max(cnt[1], cnt[2])){
encode_bit(0);
encode_bit(0);
}else if(cnt[1] >= max(cnt[0], cnt[2])){
encode_bit(1);
encode_bit(0);
swap(mp[0], mp[1]);
}else{
encode_bit(0);
encode_bit(1);
swap(mp[0], mp[2]);
}
for(ll i = 0; i < h; i++){
start = i;
final(i, -1);
}
return;
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 1005;
vector < ll > _g[N];
ll _n , _h;
vector < ll > rev = {-1, 0, 1};
void ultimate(ll s, ll p, ll D, ll source){
hops(source, s, D);
for(auto u : _g[s]){
if(u - p){
int k = decode_bit();
if(k == 0){
ultimate(u, s, D + rev[k], source);
}else{
k += decode_bit();
ultimate(u, s, D + rev[k], source);
}
}
}
return;
}
void decode(int nv, int nh) {
_n = nv;
_h = nh;
for(ll i = 1; i < _n; i++){
ll p = 0;
for(ll j = 0; j < 10; j++){
int k = decode_bit();
p |= (k << j);
}
_g[p].pb(i);
_g[i].pb(p);
}
ll pos = 0;
for(ll i = 0; i < 2; i++){
int k = decode_bit();
pos |= (k << i);
}
swap(rev[pos], rev[0]);
for(ll i = 0; i < _n; i++){
sort(_g[i].begin(), _g[i].end());
}
for(ll i = 0; i < _h; i++){
ultimate(i, -1, 0, i);
}
return;
}
