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

struct tree {
	struct tree * left, *right;
	int index;
	char name[1];
};

int next_index = 0;
struct tree * root = NULL;

struct tree * new (char * name)
{
	struct tree * ret;
	ret = calloc (1, sizeof (struct tree) + strlen (name)); 
	ret->left = ret->right = NULL;
	ret->index = next_index;
	next_index++;
	strcpy (ret->name, name);
	return ret;
}

int addtree (char * name, int * indexp)
{
	struct tree ** p = &root;
	while ((*p) != NULL) {
		int ret = strcmp (name, (*p)->name);
		if (ret < 0) {
			p = &((*p)->left);
			/* Hier stand dummerweise noch ein break, das
			 * dann die while-Schleife verlassen hat.
			 */
		} else if (ret > 0) {
			p = &((*p)->right);
			/* Hier genauso */
		} else {
			(*indexp) = (*p)->index;
			return 1;
		}
	}
	(*p) = new (name);
	(*indexp) = (*p)->index;
	return 0;
}

int depth (struct tree * t)
{
	int ret, tmp;
	if (t == NULL)
		return 0;
	ret = depth (t->left);
	tmp = depth (t->right);
	if (tmp > ret)
		ret = tmp;
	return ret+1;
}

int mindepth (int count)
{
	int ret = 0;
	while (count) {
		count >>= 1;
		ret++;
	}
	return ret;
}


int main ()
{
	char name[32];
	int idx;
	while (1) {
		fgets (name, 31, stdin);
		if (feof (stdin))
			break;
		if (name[strlen(name)-1] == '\n')
			name[strlen(name)-1] = 0;
		if (addtree (name, &idx)) {
			printf ("%s doppelt, erster Index ist %d\n", name, idx);
		}
	}
	printf ("#Elemente: %d\n", next_index);
	printf ("Tiefe: %d\n", depth (root));
	printf ("Theorische Minimaltiefe: %d\n", mindepth (next_index));
	return 0;
}