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

const int LENGTH = 30;

struct node
{
    char * name;
    char * number;
    struct node * p;
    struct node * l;
    struct node * r;
};

char print_str(char * str);
int str_comp(char * a, char * b)
{
    for (int i =0; i< LENGTH; i++)
    {
        if(a[i]!=b[i])
            if(a[i]<b[i])
                return -1;
            else
                return 1;
    }
    return 0;
}


struct node root = NULL;
int _size = 0;
void init(char * name, char * number)
{
    root.name = name;
    _size++;
    root.number = number;
    root.l = NULL;
    root.r = NULL;
    root.p = &root;
}
void add(struct node * f, char * name, char * number)
{
    if(_size==0)
    {
        init(name,number);
        return;
    }
    if (str_comp(f->name, name)>0)
    {
        if(f->l!=NULL)
        {
            add(f->l, name, number);
        }
        else
        {
            struct node* new_node = (struct node*)malloc(sizeof(struct node));
            _size++;
            new_node->l = NULL;
            new_node->r = NULL;
            new_node->name = name;
            new_node->number = number;
            new_node->p = f;
            f->l = new_node;

        }
    }
    else
    {
        if(str_comp(f->name, name)==0)
        {
            f->number = number;
            return;
        }
        if(f->r!=NULL)
        {
            add(f->r, name, number);
        }
        else
        {
            struct node* new_node = (struct node*)malloc(sizeof(struct node));
            _size++;
            new_node->l=NULL;
            new_node->r=NULL;
            new_node->name = name;
            new_node->number  = number;
            new_node->p = f;
            f->r = new_node;

        }
    }
}
void add1(char * name, char *number)
{
    struct node * k = &root;
    add(k, name, number);
}
void kill(struct node * f, char * name, struct node * parent)
{
    int cmp = str_comp(f->name, name);
    if(cmp>0)
    {
        if(f->l==NULL)
        {
            printf("NO ELEMENT\n");
            return;
        }
        kill(f->l, name, f);
        return;
    }
    if(cmp<0)
    {
        if(f->r==NULL)
        {
            printf("NO ELEMENT\n");
            return;
        }
        kill(f->r, name,f);
        return;
    }
    if(f->r==NULL&&f->l==NULL)
    {
        if(f==&root)
        {
            _size=0;
            return;
        }
        if(f->p->r==f)
        {
            parent->r = NULL;
        }
        else
        {
            parent->l = NULL;
        }
        free(f);
        _size--;
        return;
    }

    if (f->l==NULL)
    {
        struct node * tmp = f->r;
        f->l = tmp->l;
        f->r = tmp->r;
        f->name = tmp->name;
        f->number = tmp->number;
        free(tmp);
        _size--;
        return;
    }
    if(f->r==NULL)
    {
        struct node * tmp = f->l;
        f->l = tmp->l;
        f->r = tmp->r;
        f->name = tmp->name;
        f->number = tmp->number;
        free(tmp);
        _size--;
        return;
    }
    struct node * tmp = f->l;
    while(tmp->r!=NULL)
        tmp = tmp->r;
    if(tmp!=f->l)
    {
        struct node* parent = tmp->p;
        struct node* child = tmp->l;
        if(tmp->l!=NULL)
            parent->r  = child;
        else
            parent->r = NULL;
        f->name = tmp->name;
        f->number = tmp->number;
        free(tmp);
        _size--;
    }
    else
    {
        struct node* child = tmp->l;
        if(tmp->l!=NULL)
            f->l  = child;
        else
            f->l = NULL;
        f->name = tmp->name;
        f->number = tmp->number;
        free(tmp);
        _size--;
    }
}
void kill1(char * name)
{
    kill(&root, name, NULL);
}
void get_number(struct node * f, char * name)
{
    int cmp =str_comp(f->name,name);
    if(cmp>0)
    {
        if(f->l==NULL)
        {
            printf("Number not found\n");
            return;
        }
        get_number(f->l, name);
        return;
    }
    if(cmp<0)
    {
        if(f->r==NULL)
        {
            printf("Number not found\n");
            return;
        }
        get_number(f->r, name);
        return;
    }
    printf("Number is ");
    print_str(f->number);
}
void get_number1(char * name)
{
    get_number(&root, name);
}

void dfs(struct node * f)
{
    if(f->l!=NULL)
        dfs(f->l);
    printf("=======\n");
    print_str(f->name);
    print_str(f->number);
    _size++;
    printf("=======\n");
    if(f->r!=NULL)
        dfs(f->r);
}

void dfs1()
{
    if(_size==0)
    {
        printf("NO ELEMENTS\n");
    }
    else
    {
        _size=0;
        dfs(&root);
    }
}

char print_str(char * str)
{
    for (int i =0; i<LENGTH; i++)
        printf("%c",str[i]);
    printf("\n");
}

char * readString()
{
    char* arr= (char*)malloc(LENGTH*sizeof(char));
    for (int  i=0; i<LENGTH; i++)
        arr[i]=' ';
    char ch = getchar();
    int i=0;
    while(ch!=' '&&ch!='\n')
    {
        arr[i++]=ch;
        ch = getchar();
    }
    if(i)
        return arr;
    else
        return readString();
}

int eq(char *a, char *b)
{
    for (int i =0; i<3; i++)
        if(a[i]!=b[i])
            return 0;
    return 1;
}


int main()
{
    char * str = readString();
    while(!eq(str, "end"))
    {
        if(eq(str, "add"))
        {
            printf("name is ");
            char * name = readString();
            printf("number is ");
            char * num = readString();
            add1(name,num);
        }
        else if(eq(str, "del"))
        {
            printf("name is ");
            char * name = readString();
            kill1(name);
            printf("done\n");
        }
        else if(eq(str, "get"))
        {
            printf("name is ");
            char * name = readString();
            get_number1(name);
        }
        else if(eq(str,"dfs"))
        {
            dfs1();
        }
        str = readString();
    }

    return 0;
}