#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 256

typedef struct tree {
    char value[SIZE];
    struct tree *left;
    struct tree *right;
} Tree;

int valid_db = 1;

//odstranit koncovy znak
void strip_newline(char *s) {
    int len = strlen(s);
    if (len > 0 && s[len-1] == '\n')
        s[len-1] = '\0';
}

// rekurzivne nacitanie stromu v preorder
Tree* read_tree() {
    char buffer[SIZE];

    if (!fgets(buffer, SIZE, stdin))
        return NULL;

    // prazdny riadok -> koniec
    if (strcmp(buffer, "\n") == 0)
        return NULL;

    strip_newline(buffer);

    Tree *node = calloc(1, sizeof(Tree));
    if (!node) exit(1);

    strcpy(node->value, buffer);

    // odpoved -> list
    if (buffer[0] == '*') {
        return node;
    }

    // inak nacitat oboch potomkov
    node->left = read_tree();
    if (!node->left) {
	valid_db = 0;
        free(node);
        return NULL;
    }

    node->right = read_tree();
    if (!node->right) {
        free(node->left);
	valid_db = 0;
        free(node);
        return NULL;
    }

    return node;
}

// uvolnenie pamate
void destroy_tree(Tree *t) {
    if (!t) return;
    destroy_tree(t->left);
    destroy_tree(t->right);
    free(t);
}

// pocet listov = pocet tovarov 
int count_leaves(Tree *t) {
    if (!t) return 0;
    if (!t->left && !t->right)
        return 1;
    return count_leaves(t->left) + count_leaves(t->right);
}

// spustenie znalostneho systemu
void run_system(Tree *node) {
    if (!node) return;

    printf("%s\n", node->value);

    // list -> koniec
    if (!node->left && !node->right) {
	printf("Koniec\n");
        return;
    }

    int c;

    do {
	    c = getchar();
	    if (c == EOF) {
		    printf("Koniec vstupu\n");
		    return;
	    }
    } while (c=='\n'  || c=='\r' || c==' ' || c=='\t');

    if (c == 'a') {
        run_system(node->left);
    } else if (c == 'n') {
        run_system(node->right);
    } else {
        printf("Nerozumiem\n");
    }
}

int main() {
    Tree *root = read_tree();

    // nepodarilo sa nacitat koren -> chyba
    if (!root || !valid_db) {
        printf("Expert z bufetu to vie.\n");
	printf("Chybna databaza\n");
        return 0;
    }

    // skontrolovat prazdny riadok
    char buffer[SIZE];
    if (!fgets(buffer, SIZE, stdin) || strcmp(buffer, "\n") != 0) {
        printf("Koniec vstupu\n");
        destroy_tree(root);
        return 0;
    }

    int leaves = count_leaves(root);

    printf("Expert z bufetu to vie.\n");
    printf("Pozna %d druhov ovocia a zeleniny.\n", leaves);
    printf("Odpovedajte 'a' pre prvu moznost alebo 'n' pre druhu moznost.\n");

    run_system(root);

    destroy_tree(root);
    return 0;
}