#include <iostream>
#include <string>
#define MAX_ELEMENTS 100000
 
using namespace std;
 
struct node {
  string label;
  int child, sibling;
};
 
struct tree {
  node nodes[MAX_ELEMENTS];
  int root;
};
 
tree *tree_init(int root) {
  tree *T = new tree;
  T->root = root;
  T->nodes[root].child =  -1;
  T->nodes[root].sibling =  -1;
 
  return T;
}
 
node *node_init(int n, string label, int child, int sibling, tree *T) {
  node *x = new node;
  x->label = label;
  x->child = child;
  x->sibling = sibling;
  T->nodes[n] = *x;
 
  return x;
}
 
string node_label(int n, tree *T) {
  return T->nodes[n].label;
}
 
void node_set_label(int n, const string label, tree *T) {
  T->nodes[n].label = label;
}
 
int tree_root(tree *T) {
  return T->root;
}
 
int tree_parent(int n, tree *T) {
  if(n == T->root)
    return -1;
 
  for(int m = 0; m < MAX_ELEMENTS; m++)
    if(T->nodes[m].child == n)
      return m;
    else if(T->nodes[m].sibling == n)
      return tree_parent(m, T);
 
  return -1;
}
 
int tree_first_child(int n, tree *T) {
  return T->nodes[n].child;
}
 
int tree_next_sibling(int n, tree *T) {
  return T->nodes[n].sibling;
}
 
int tree_insert_node(int n, int N, tree *T) {
  node link = T->nodes[n];
  if(link.child == -1) {
    link.child = N;
    return n;
  }
 
  while(link.sibling != -1)
    link = T->nodes[link.sibling];
 
  link.sibling = N;
  return n;
}
 
void tree_delete_node(int n, tree *T, bool destructive) {
  node N = T->nodes[n];
  if(destructive) {
    if(N.child != -1)
      tree_delete_node(N.child, T, true);
    if(N.sibling != -1)
      tree_delete_node(N.sibling, T, true);
  }
 
  delete &N;
}
 
void tree_delete_node(int n, tree *T) {
  node N = T->nodes[n];
  if(N.child != -1)
    tree_delete_node(N.child, T, true);
 
  int parentN = tree_parent(n, T);
  if(parentN == -1)
    return;
 
  node parent = T->nodes[parentN];
  if(parent.child == n)
    parent.child = N.sibling;
  else {
    node prev = T->nodes[parent.child];
    while(prev.sibling != n)
      prev = T->nodes[prev.sibling];
    prev.sibling = N.sibling;
  }
 
  delete &N;
}