#include "dungeon2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 200 + 7;
int p3[N];
int dis[N], ans[N];
int in[N], out[N];
int cur[N];
vector<int> ed[N], up[N], val[N];
vector<int> drz[N];
int cnt = 0;

void DoP3(int n)
{
    p3[0] = 1;
    for(int i = 1; i <= n; ++i)
        p3[i] = p3[i - 1] * 3;
}

void DFS(int v)
{
    int m = NumberOfRoads();
    in[v] = LastRoad();
    //cout << "dfs: " << v << " " << m << "\n";
    //cout << v << "\n";
    for(int i = 1; i <= m; ++i)
    {
        if(i == in[v]) continue;
        Move(i, 2);
        int cba = LastRoad();
        if(Color() == 2)
        {
            up[v].pb(i);
            val[v].pb(0);
        }
        if(Color() == 1)
        {
            ++cnt;
            int ne = cnt;
            ed[v].pb(ne); ed[ne].pb(v);
            drz[v].pb(ne);
            out[ne] = i;
        
            DFS(ne);
        }
        Move(cba, 3);
    }
}

void DFSR(int v, int r)
{
    for(int i = 0; i < (int)up[v].size(); ++i)
    {
        Move(up[v][i], 1);
        val[v][i] += p3[r] * (Color() - 1);
        Move(LastRoad(), Color());
    }
    for(int i = 0; i < (int)drz[v].size(); ++i)
    {
        Move(out[drz[v][i]], (cur[v] % 3) + 1);
        DFSR(drz[v][i], r);
        Move(in[drz[v][i]], 1);
    }
    cur[v] /= 3;
}

void BFS(int s)
{
    int v;
    queue<int> q;
    for(int i = 1; i <= cnt; ++i) dis[i] = cnt * 10;
    dis[s] = 0;
    q.push(s);
    while(q.size())
    {
        v = q.front(); q.pop();
        ++ans[dis[v]];
        for(int i = 0; i < ed[v].size(); ++i)
            if(dis[ed[v][i]] > dis[v] + 1)
            {
                dis[ed[v][i]] = dis[v] + 1;
                q.push(ed[v][i]);
            }
    }
}

void Inspect(int R)
{
    DoP3(6);
    cnt = 1;
    DFS(1);

    /*
    for(int i = 1; i <= cnt; ++i)
    {
        cout << "new: " << i << " " << drz[i].size() << " " << up[i].size() << "\ndrz: ";
        for(int j = 0; j < (int)drz[i].size(); ++j)
            cout << drz[i][j] << " ";
        cout << "\nup:";
        for(int j = 0; j < (int)up[i].size(); ++j)
            cout << up[i][j] << " ";
        cout << "\n";
    }*/

    for(int i = 1; i <= cnt; ++i)
        cur[i] = i;
    for(int i = 0; i < 5; ++i)
        DFSR(1, i);

    for(int i = 1; i <= cnt; ++i)
        for(int j = 0; j < (int)up[i].size(); ++j)
        {
            ed[i].pb(val[i][j]);
            ed[val[i][j]].pb(i);
        }

    for(int i = 1; i <= cnt; ++i)
        BFS(i);


    for(int i = 1; i <= R; ++i)
        Answer(i, ans[i] / 2);
}