#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=207;

vector<int>G[N];
vector<int>G1[N];
int ile[N][N];
bool is[N][N];
bool skip[N][N];
bool go[N][N];
int M[N];
int O[N];

vector<int>val={1,2,3};

int it;


void dfs_init(int v)
{
	O[v]=LastRoad();
	if(v!=1) 
	{
		is[v][LastRoad()]=1;
		skip[v][LastRoad()]=1;
	}
	int m=NumberOfRoads();
	M[v]=m;
	FOR(i,1,m)
	{
		if(i==LastRoad()&&v!=1) continue;
		Move(i,2);
		if(Color()==1)
		{
			is[v][i]=1;
			go[v][i]=1;
			it++;
			G[v].pb(it);
			dfs_init(it);
		}
		else 
		{
			if(Color()==3) skip[v][i]=1;
			Move(LastRoad(),Color());
		}
	}
	if(v!=1) Move(O[v],3);
}

int get(int x,int j)
{
	while(j--) x/=3;
	return x%3;
}

int pot;

void dfs(int v,int j,int d)
{
	int m=NumberOfRoads();
	debug(v);
	FOR(i,1,m)
	{
		if(skip[v][i]) continue;
		if(j!=0&&d<=(1<<j)+ile[v][i]&&!is[v][i]) continue;
		Move(i,get(d,j)+1);
		if(go[v][i])
		{
			it++;
			debug(i);
			dfs(it,j,d+1);
		}
		else
		{
			ile[v][i]+=(Color()-1)*pot;
			Move(LastRoad(),Color());
		}
	}
	if(v!=1) Move(O[v],3);
}

vector<int>ord;
int xd[N];
vector<pair<int,int>>E;

void dfs1(int v,int d)
{
	ord.pb(v);
	for(auto u:G[v])
	{
		dfs1(u,d+1);
		E.pb({u,v});
	}
	debug(v,M[v]);
	FOR(i,1,M[v])
	{
		debug(is[v][i],ile[v][i]);
		if(!is[v][i]) 
		{
			if(ile[v][i]==0&&xd[v]>0) xd[v]--; 
			else 
			{
				E.pb({v,ord[ile[v][i]]});
				debug(v,ord[ile[v][i]]);
				xd[ord[ile[v][i]]]++;
			}
		}
	}
	ord.pop_back();
}

int ans[N];
int D[N];

void Inspect(int R)
{
	int n;
	it=1;
	dfs_init(1);
	n=it;
	pot=1;
	FOR(j,0,5)
	{
		it=1;
		dfs(1,j,0);
		swap(val[0],val[2]);
		pot*=3;
	}
	dfs1(1,0);
	debug(E);
	for(auto [u,v]:E) 
	{
		G[u].pb(v);
		G[v].pb(u);
	}
	FOR(i,1,n)
	{
		deque<int>Q;
		Q.pb(i);
		FOR(j,1,n) D[j]=inf;
		D[i]=0;
		while(sz(Q)>0)
		{
			int v=Q[0];
			Q.pop_front();
			ans[D[v]]++;
			for(auto u:G[v])
			{
				if(D[u]==inf)
				{
					D[u]=D[v]+1;
					Q.pb(u);
				}
			}
		}
	}
	FOR(i,1,R)
	{
		debug(i,ans[i]);
		Answer(i,ans[i]/2);
	}
}