#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int grpsiz = 3;
int grpbits = ceil(log2(((int)pow(3,grpsiz))));
void writeInt(int x, int bits){
for(int i = 0;i<bits;i++){
if((1<<i)&x)
encode_bit(1);
else
encode_bit(0);
}
}
void bfsupdate(int x, vector<int>g[], int par[], int dist[]){
bool vis[n];
fill(vis,vis+n,0);
queue<int>q;
q.push(x);
dist[x]=0;
vis[x]=1;
while(!q.empty()){
int nx = q.front();
q.pop();
for(int i : g[nx]){
if(vis[i])
continue;
vis[i]=1;
par[i]=nx;
q.push(i);
dist[i]=dist[nx]+1;
}
}
}
void bfs(int x, vector<int>g[], int dist[]){
bool vis[n];
fill(vis,vis+n,0);
queue<int>q;
q.push(x);
dist[x]=0;
vis[x]=1;
while(!q.empty()){
int nx = q.front();
q.pop();
for(int i : g[nx]){
if(vis[i])
continue;
vis[i]=1;
q.push(i);
dist[i]=dist[nx]+1;
}
}
}
int encodeGroup(vector<int>grp){
int ans = 0;
for(int i = 0;i<grpsiz;i++){
ans+=((int)pow(3,i))*(grp[i]+1);
}
return ans;
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
n=nv;
vector<int>g[n];
for(int i = 0;i<ne;i++){
g[v1[i]].push_back(v2[i]);
g[v2[i]].push_back(v1[i]);
}
int par[n];
int dist[n];
bfsupdate(0,g,par,dist);
for(int i = 1;i<n;i++){
writeInt(par[i],10);
}
//parent arr sent
for(int h = 1;h<nh;h++){
bfs(h,g,dist);
for(int i = 1;i<n;i+=grpsiz){
vector<int>group(grpsiz);
for(int j = 0;j<grpsiz&&(i+j)<n;j++){
group[j]=dist[i+j]-dist[par[i+j]];
assert(abs(group[j])<=1);
}
writeInt(encodeGroup(group),grpbits);
}
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
int n2;
const int grpsiz2 = 3;
int grpbits2 = ceil(log2(((int)pow(3,grpsiz2))));
int readInt(int bits){
int ans = 0;
for(int i = 0;i<bits;i++){
if(decode_bit()){
ans+=(1<<i);
}
}
return ans;
}
vector<int> decodeGroup(int x){
vector<int>grp(grpsiz2);
int ind = 0;
while(x){
grp[ind++]=(x%3)-1;
x/=3;
}
while(ind<grpsiz2){
grp[ind++]=-1;
}
return grp;
}
void dfs(int st, vector<array<int,2>>g[], int dist[], int p, int d, int par[]){
par[st]=p;
dist[st]=d;
for(array<int,2>e:g[st]){
if(e[0]==p)
continue;
dfs(e[0],g,dist,st,d+e[1],par);
}
}
void decode(int nv, int nh) {
n2=nv;
vector<array<int,2>>g[n2];
for(int i = 1;i<n2;i++){
int p = readInt(10);
g[i].push_back({p,1});
g[p].push_back({i,1});
}
int dist[n2];
int par[n2];
dfs(0,g,dist,-1,0, par);
for(int i = 0;i<n2;i++){
hops(0,i,dist[i]);
}
int temp[n2];
for(int h = 1;h<nh;h++){
for(int i = 0;i<n2;i++){
g[i].clear();
}
for(int i = 1;i<n2;i+=grpsiz2){
vector<int>grp = decodeGroup(readInt(grpbits2));
for(int j = 0;j<grpsiz2&&(i+j)<n2;j++){
g[i+j].push_back({par[i+j],-grp[j]});
g[par[i+j]].push_back({i+j,grp[j]});
}
}
dfs(h,g,dist,-1,0,temp);
for(int i = 0;i<n2;i++){
hops(h,i,dist[i]);
}
}
}
