#include <stdio.h>   // knižnica pre vstup a výstup (printf, fgets)
#include <stdlib.h>  // knižnica pre malloc, free
#include <string.h>  // knižnica pre prácu s reťazcami (strdup, strcspn)

#define MAX 256     // maximálna dĺžka jednej riadky

// definícia uzla stromu
typedef struct Node {
    char *t;           // text otázky alebo odpovede
    int leaf;          // 1 = list (odpoveď), 0 = otázka
    struct Node *a;    // ukazovateľ na "áno" podstrom
    struct Node *n;    // ukazovateľ na "nie" podstrom
} Node;

char s[MAX];          // buffer pre načítanie jednej riadky

// funkcia na načítanie stromu zo vstupu
Node* readTree() {
    // načítame riadok, ak EOF alebo prázdny riadok, vrátime NULL
    if (!fgets(s, MAX, stdin) || s[0]=='\n') return NULL;

    // odstránime znak nového riadku \n
    s[strcspn(s, "\n")] = 0;

    // vytvoríme nový uzol
    Node *x = calloc(1, sizeof(Node));

    // nastavíme, či je list: ak riadok začína *, je to list
    x->leaf = s[0]=='*';

    // uložíme text: ak list, preskočíme *, inak uložíme celý riadok
    x->t = strdup(s + (s[0]=='*' ? 1 : 0));

    // ak nie je list, načítame podstromy áno a nie
    if (!x->leaf) x->a = readTree(), x->n = readTree();

    return x;  // vrátime uzol
}

// funkcia na spočítanie listov v strome
int count(Node *x) {
    if (!x) return 0;                 // prázdny uzol = 0
    return x->leaf ? 1 : count(x->a) + count(x->n); // ak list, +1, inak spočítame podstromy
}

// funkcia pre spustenie chatbota
void run(Node *x) {
    if (!x) return;                   // prázdny uzol - nič nerobíme

    if (x->leaf) {                    // ak sme na liste (odpoveď)
        printf("*%s\nKoniec\n", x->t);  // vypíšeme odpoveď a koniec
        return;
    }

    printf("%s\n", x->t);             // vypíšeme otázku

    if (!fgets(s, MAX, stdin)) {      // načítame odpoveď od používateľa
        printf("Koniec vstupu\n");  // ak nič, upozorníme
        return;
    }

    char c = s[0];                     // berieme prvý znak odpovede

    // jednoduché if-else pre spracovanie odpovede
    if (c == 'a') {
        run(x->a);                     // ak áno, pokračujeme v ľavom podstrome
    } else if (c == 'n') {
        run(x->n);                     // ak nie, pokračujeme v pravom podstrome
    } else {
        printf("Nerozumiem\n");  // iná odpoveď nie je platná
    }
}

// funkcia na uvoľnenie pamäte stromu
void freeTree(Node *x) {
    if (!x) return;                   // prázdny uzol - nič nerobíme
    freeTree(x->a);                   // uvoľníme ľavý podstrom
    freeTree(x->n);                   // uvoľníme pravý podstrom
    free(x->t);                        // uvoľníme text
    free(x);                           // uvoľníme uzol
}

// hlavná funkcia
int main() {
    Node *root = readTree();          // načítame strom zo vstupu
     printf("Expert z bufetu to vie.\n"); // vždy vypíšeme tento riadok

    if (!root) {                    // ak strom je prázdny alebo chybne načítaný
        printf("Chybna databaza\n");
        return 0;
    }    
    fgets(s, MAX, stdin);             // prečítame prázdny riadok medzi databázou a vstupom používateľa

    int k = count(root);              // spočítame počet listov (druhov tovaru)
     
    printf("Pozna %d druhov ovocia a zeleniny.\n", k);
    printf("Odpovedajte 'a' pre prvu moznost alebo 'n' pre druhu moznost.\n");

    run(root);                        // spustíme chatbota

    freeTree(root);                   // uvoľníme celú pamäť stromu

    return 0;                         // koniec programu
}