#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int counter=0, depth[205], vect[205], twok[205][20], mult=1, tt;
vector<int> graph[205], pd[205], adj[205];
void dfs(int node, int p, int d){
int par=LastRoad();
if (Color()!=1){
--counter;
if (Color()==2)tt=-1;
else tt=-2;
Move(par, Color());
return;
}
twok[node][0]=p;
for (int i=1; i<20; ++i)twok[node][i]=twok[twok[node][i-1]][i-1];
depth[node]=d;
pd[node].resize(NumberOfRoads()+1, 0);
for (int i=1; i<=NumberOfRoads(); ++i){
if (i==par){
if (p!=node)graph[node].pb(p);
}
else{
int temp=counter;
Move(i, 2);
dfs(++counter, node, d+1);
if (temp==counter)graph[node].pb(tt);
else graph[node].pb(temp+1);
}
}
if (par!=-1)Move(par, 3);
}
void dfs2(int node){
int par=LastRoad();
for (int i=1; i<=NumberOfRoads(); ++i)if (i!=par){
if (graph[node][i-1]==-1){
Move(i, vect[node]);
pd[node][i]+=mult*(Color()-1);
Move(LastRoad(), Color());
}
else if (graph[node][i-1]!=-2)Move(i, vect[node]), dfs2(graph[node][i-1]);
}
if (par!=-1)Move(par, vect[node]);
}
int kth(int a, int k){
for (int i=0; i<20; ++i)if (k&(1<<i))a=twok[a][i];
return a;
}
void Inspect(int R){
dfs(0, 0, 0);
for (int b=0; b<5; ++b, mult*=3){
for (int i=0; i<=counter; ++i)vect[i]=(depth[i]/mult)%3+1;
dfs2(0);
}
for (int i=0; i<=counter; ++i)for (int j=0; j<graph[i].size(); ++j){
if (graph[i][j]==-1){
adj[i].pb(kth(i, depth[i]-pd[i][j+1]));
adj[kth(i, depth[i]-pd[i][j+1])].pb(i);
}
else if (graph[i][j]!=-2)adj[i].pb(graph[i][j]);
}
vector<int> ans(max(R, counter)+1, 0);
for (int i=0; i<=counter; ++i){
queue<int> q;
vector<int> dj(counter+1, -1);
dj[i]=0;
q.push(i);
while (q.size()){
int node=q.front();
q.pop();
for (auto num:adj[node])if (dj[num]==-1)dj[num]=dj[node]+1, q.push(num);
}
for (int j=0; j<=counter; ++j)++ans[dj[j]];
}
for (int i=1; i<=R; ++i)Answer(i, ans[i]/2);
}
