#include <bits/stdc++.h>
#include "dungeon2.h"
using namespace std;
// na co wskazuje i jakim numerem mozna sie tam dostac
short n;
//vector <pair <short, short>> sasiedzi[201];
short dokad_prowadzi[201][200];
short ile_korytarzy[201];
bool czy_w_gore[201][200];
short czym_wrocilismy[201][200];
bool czy_sasiad[201][200];
short ojcowie_numer[201];
// 1 to nieodwiedzony, 3 to odwiedzony i czesc drogi, 2 to odwiedzony i nie czesc drogi
short ktory_bit;
int odpowiedzi[201];
short zaglebienie[201];
void dfs_drzewowy() {
    int kolor = n;
    n++;
    ile_korytarzy[kolor] = NumberOfRoads();
    for (short i = 1; i <= ile_korytarzy[kolor]; i++) {
        if (ojcowie_numer[kolor] == i) continue;
        Move(i, 3);
        int jak_wrocic = LastRoad();
        if (Color() == 1) {
            //sasiedzi[kolor].push_back({n, i});
            czy_sasiad[kolor][i] = true;
            ojcowie_numer[n] = jak_wrocic;
            dokad_prowadzi[kolor][i] = n;
            dokad_prowadzi[n][jak_wrocic] = kolor;
            dfs_drzewowy();
            Move(jak_wrocic, 2);
        }
        else if (Color() == 3) {
            Move(jak_wrocic, 3);
            czy_w_gore[kolor][i] = true;
            czym_wrocilismy[kolor][i] = jak_wrocic;
        }
        else {
            Move(jak_wrocic, 2);
        }  
    }
}
// w systemie trojkowym, potega bedzie od 0 do 4
short jaki_bit_zapalony(short liczba, short potega) {
    while (potega) {
        potega--;
        liczba /= 3;
    }
    return liczba % 3;
}
short potega3(short potega) {
    if (potega == 0) return 1;
    if (potega == 1) return 3;
    if (potega == 2) return 9;
    if (potega == 3) return 27;
    return 81;
}
void dfs_krawedziowy(short v) {
    short jaki_kolor = jaki_bit_zapalony(v, ktory_bit);
    for (short i = 1; i <= ile_korytarzy[v]; i++) {
        if (czy_sasiad[v][i]) {
            Move(i, jaki_kolor);
            dfs_krawedziowy(dokad_prowadzi[v][i]);
            Move(ojcowie_numer[dokad_prowadzi[v][i]], Color());
        }
        else if (czy_w_gore[v][i]) {
            Move(i, jaki_kolor);
            dokad_prowadzi[v][i] += potega3(ktory_bit) * Color();
            Move(LastRoad(), Color());
        }
    }
}
void zrob_dfsy_krawedziowe() {
    dfs_krawedziowy(1);
    ktory_bit++;
    dfs_krawedziowy(1);
    ktory_bit++;
    dfs_krawedziowy(1);
    ktory_bit++;
    dfs_krawedziowy(1);
    ktory_bit++;
    dfs_krawedziowy(1);
}
void skonstuuj_reszte_krawedzi() {
    for (short v = 1; v <= n; v++) {
        for (short i = 1; i <= ile_korytarzy[v]; i++) {
            if (czy_w_gore[v][i]) dokad_prowadzi[dokad_prowadzi[v][i]][czym_wrocilismy[v][i]] = v;
        }
    }
}
void bfs_szukajacy(short x) {
    fill(zaglebienie + 1, zaglebienie + n + 1, -1);
    queue <short> kolejka;
    zaglebienie[x] = 0;
    kolejka.push(x);
    while (!kolejka.empty()) {
        short v = kolejka.front();
        kolejka.pop();
        for (short i = 1; i <= ile_korytarzy[v]; i++) {
            if (zaglebienie[dokad_prowadzi[v][i]] != -1) continue;
            zaglebienie[dokad_prowadzi[v][i]] = zaglebienie[v] + 1;
            odpowiedzi[zaglebienie[dokad_prowadzi[v][i]]]++;
            kolejka.push(dokad_prowadzi[v][i]);
        }
    }
}
void zrob_bfsy_szukajace() {
    for (short i = 1; i <= n; i++) {
        bfs_szukajacy(i);
    }
}
void Inspect(int R) {
    n = 1;
    dfs_drzewowy();
    zrob_dfsy_krawedziowe();
    skonstuuj_reszte_krawedzi();
    zrob_bfsy_szukajace();
    for (short i = 1; i <= R; i++) Answer(i, odpowiedzi[i] / 2);
}