#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
const int N=1e3;
vector<int> adj[N];
vector<int> nadj[N];
int par[N];
int vis[N];
void dfs(int u, int p) {
if (vis[u]) return;
vis[u]=1;
par[u]=p;
for(auto&v:adj[u]) {
if (v==p) continue;
dfs(v,u);
}
}
void encode(int n, int h, int p, int a[], int b[]) {
forn(i,p) {
int u=a[i], v=b[i];
adj[u].pb(v), adj[v].pb(u);
}
dfs(0,0);
forn(i,n) forn(j,10) encode_bit((par[i]>>j)&1);
vector<int> d, vis;
forn(i,h) {
d.assign(n,0), vis.assign(n,0);
queue<int> q; q.push(i); vis[i]=1;
while (q.size()) {
auto u=q.front(); q.pop();
for(auto&v:adj[u]) {
if (vis[v]) continue;
vis[v]=1;
d[v]=d[u]+1;
q.push(v);
}
}
for (int i=0; i<n; i+=5) {
int x=0, t=1;
for (int j=i; j<min(i+5,n); ++j) {
if (d[i]==d[par[i]]+1) {
x+=t;
} else if (d[i]==d[par[i]]-1) {
x+=2*t;
}
t*=3;
}
forn(j,8) encode_bit((x>>j)&1);
}
}
}
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
const int N=1e3;
vector<int> adj[N];
vector<int> nadj[N];
int par[N];
int type[N];
int d[N];
void restore(int u, int p) {
for(auto&v:adj[u]) {
if (v==p) continue;
if (v==par[u]) {
if (type[u]==0) {
d[v]=d[u];
} else if (type[u]==1) {
d[v]=d[u]-1;
} else {
d[v]=d[u]+1;
}
} else {
if (type[v]==0) {
d[v]=d[u];
} else if (type[v]==1) {
d[v]=d[u]+1;
} else {
d[v]=d[u]-1;
}
}
restore(v,u);
}
}
void decode(int n, int h) {
forn(i,n) forn(j,10) par[i]|=decode_bit()<<j;
forn(i,n) if (i) {
adj[i].pb(par[i]);
adj[par[i]].pb(i);
}
forn(u,h) {
forn(i,n) d[i]=0;
for(int i=0; i<n; i+=5) {
int x=0;
forn(j,8) x|=decode_bit()<<j;
for (int j=i; j<min(i+5,n); ++j) {
type[j]=x%3;
x/=3;
}
}
restore(u,-1);
forn(i,n) hops(u,i,d[i]);
}
}
