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

typedef struct tree_item_tag {
	const char * word; 
	size_t count;
	struct tree_item_tag *left, *right, *parent;
} tree_item_t;

void insert(tree_item_t** first_item, const char* keyword, size_t * count) {
	
	tree_item_t** pcur = first_item, **prev =  first_item; 
	int cmp_words;
	
	while (*pcur != NULL) { /* searching for already inserted word inc count */
		if((cmp_words=strcmp(keyword, (*pcur)->word)) == 0) {
			++(*pcur)->count;
			return;
        }  
        prev = pcur;
		pcur=(cmp_words<0) ? &((*pcur)->left) : &((*pcur)->right);
    } /* it is the first insert of this word */
	*pcur = malloc( sizeof(tree_item_t) );
    (*pcur)->word = strcpy( malloc( strlen(keyword) + 1) , keyword);
    (*pcur)->count = 1;
    (*pcur)->parent = *prev;
    (*pcur)->left = (*pcur)->right = NULL;  
    ++(*count);
}

void printnotrec(tree_item_t* tree_item, size_t count) {
	
	size_t cur_count = 0;
	tree_item_t * pcur = tree_item, * pprev = pcur, *tmppcur;
	
	while(cur_count != count) {
		tmppcur = pcur;
		if( (pcur->left==NULL && pprev!=pcur->right)
		||pprev==pcur->left) {
			(void)printf("%s %d\n",pcur->word, pcur->count);
			++cur_count;
			if( pcur->right == NULL ) {
				if( pcur->parent->right == pcur ) {
					pprev = pcur->parent;
					pcur = pcur->parent->parent;
					continue;
				} else 
					pcur = pcur->parent;
			} else 
				pcur = pcur->right;
		}
		else {
			if(pprev == pcur->right)
				pcur = pcur->parent;
			else 
				pcur = pcur->left;
		}
		pprev = tmppcur;
	}
}

int get_word(char * buf_word, size_t buf_size) {
	
	int c; /* current read symbol */
	size_t word_len = 0;
	
	while( (c=getchar()) != EOF) {
		if(isalpha( (unsigned char) c) || (word_len > 0 && c == '\'')) {
			buf_word[ word_len++ ] = (unsigned char) tolower(c);
			if(word_len + 1 == buf_size) break; /* return only part of word */
		} else if(word_len > 0) break; /* word can be returned */
	}  
	if(word_len > 0) {
		buf_word[ word_len ]= '\0';
		return 1;
	} else return 0;
}

int main(void) {
	
	tree_item_t *first_item = NULL;
	size_t buf_size = 50; /* must be bigger than 1 */
	size_t count = 0;
	char * buf_word = malloc(buf_size);
	
	while(get_word(buf_word, buf_size)) 
		insert(&first_item, buf_word,&count);
	
	printnotrec(first_item,count);
	printf("%d\n",count);
	return EXIT_SUCCESS;
}