#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <iomanip>
#include <iostream>
using namespace std;

struct Node {
int size;
int key;
struct Node *son;
struct Node *brother;
};
void repeat(char c, int n) {for (int i = 0; i < n; i++) cout << c;}
void PRINT(struct Node *tree, int space) {
repeat(' ', 2*space);
cout << tree->key << endl;
if (tree->brother == NULL && tree->son == NULL) return;
if (tree->son != NULL)
{
PRINT(tree->son, space + 1);
}
if (tree->brother != NULL) {
tree = tree->brother;
PRINT(tree, space);
}
return;
}
int update(struct Node *tree) {
if (tree->brother == NULL && tree->son == NULL) {
tree->size = 1;
}
if (tree->son != NULL)
{
update(tree->son);
tree->size = tree->son->size + 1;
}
if (tree->brother != NULL) {
update(tree->brother);
tree->size = max(tree->brother->size, tree->size);
}
return tree->size;
}
struct Node *create_tree(int v) {
struct Node *Tree = (struct Node *) malloc(sizeof(struct Node));
Tree->key = v;
Tree->son = NULL;
Tree->brother = NULL;
Tree->size = 1;
return Tree;
}

struct Node *to_son(struct Node *tree) {
return tree->son;
}

struct Node *to_brother(struct Node *tree) {
return tree->brother;
}

struct Node *last_son(struct Node *it) {
it = it->son;
while (it->brother != NULL) {
it = it->brother;
cout << it->key << endl;
}
return it;
}
bool destroy(struct Node *tree, struct Node *it) {
if (it == NULL)
return false;
destroy(tree, it->son);
if (tree != it)
destroy(tree, it->brother);
free(it);
return true;
}

struct Node* find_del(struct Node *tree, int value) {
struct Node *it = tree, *t;
if (it->son->key == value)
{
t = it->son;
it->son = t->brother;
t->brother = NULL;
if (destroy(t, t))
return tree;
else
return NULL;
}
else
{
it = it->son;
while (it->brother != NULL) {
if (it->brother->key == value) {
t = it->brother;
it->brother = t->brother;
t->brother = NULL;
if (destroy(t, t))
return tree;
else
return NULL;
}
it = it->brother; }
}
return NULL;
}
struct Node* add_node(struct Node* &tree, const string& a) {
int n = a.size();
struct Node* t = tree;
int value;
cin >> value;
int i = 0;
while (++i < n) {
if (a[i] == 'r') {
tree = create_tree(value);
return tree;
}
if (a[i] == 's') {
if (t = to_son(t))
continue;
return NULL;
}
if (a[i] == 'b') {
if (t = to_brother(t))
continue;
return NULL;
}
}
if (t->son != NULL) {
t = last_son(t);
t->brother = create_tree(value);
return t->brother;
}
else {
t->son = create_tree(value);
return t->son;
}
}
struct Node* del_node(struct Node* &tree, const string& a) {
int n = a.size();
struct Node* t = tree;
int value;
cin >> value;
int i = 0;
while (++i < n) {
if (a[i] == 's') {
if (t = to_son(t))
continue;
return NULL;
}
if (a[i] == 'b') {
if (t = to_brother(t))
continue;
return NULL;
}
}
if (t->son != NULL) {
return find_del(t, value);}
return NULL;
}
bool destroyTree(struct Node* &it) {

if (it == NULL)
return false;
destroyTree(it->son);
destroyTree(it->brother);
free(it);
it = NULL;
return true;
}
int main()
{

struct Node *tree = NULL;
struct Node *ex =NULL;
string a;
while (cin >> a) {
if (a[0] == '+') {
if (add_node(tree, a) == NULL)
cout << "NO" << endl;
else
cout << "OK" << endl;
}
if (a[0] == 'p') {
if (tree == NULL)
cout << "empty" << endl;
else
PRINT(tree, 0);
}
if (a[0] == '-') {
if (a[1] == 'r') {
if (destroyTree(tree))
cout << "OK" << endl;
else
cout << "NO" << endl;
continue;
}
if (del_node(tree, a) == NULL)
cout << "NO" << endl;
else
cout << "OK" << endl;
}
if (a[0] == 't') {
if (tree == NULL) {
cout << "Tree no created" << endl;
continue;
}
cout << update(tree) << endl;
}
}
return 0;
}