#include <utility>
#include <algorithm>
#include <iostream>
#include <vector>
#include <optional>

namespace library {

using node_ref = std::size_t;

enum direction { down, up };
template <typename T> struct node_t;
template <typename T> struct forest_iterator;
template <typename T> struct child_iterator;

template <typename T>
struct forest {
  node_ref add(T value);
  node_ref add_child(node_ref ref, T value);
  node_ref add_sibling(node_ref ref, T value);
  node_ref remove(node_ref ref);

  forest_iterator<T> begin() {
    if (!pool.size()) return forest_iterator<T>();
    // assume root will always be in the 0 index
    return forest_iterator<T>(this, node_ref(0), node_ref(0));
  }
  forest_iterator<T> end() {
    if (!pool.size()) return forest_iterator<T>();
    // assume root will always be in the 0 index
    return forest_iterator<T>(this, node(0).a12, node_ref(0));
  }

  forest_iterator<T> begin(node_ref ref) { return forest_iterator<T>(this, ref, node(ref).a11); }
  forest_iterator<T> end(node_ref ref) { return forest_iterator<T>(this, node(ref).a12, ref); }

  child_iterator<T> begin_child(node_ref ref = 0) {
    if (!pool.size()) return child_iterator<T>();
    return child_iterator<T>(this, node(ref).a21, ref);
  }
  child_iterator<T> end_child(node_ref ref = 0) {
    if (!pool.size()) return child_iterator<T>();
    return child_iterator<T>(this, ref, node(ref).a22);
  }

  node_ref next_free(T&& value) {
    auto p = try_used_space();
    if (p) {
      pool[*p] = node_t<T> {std::forward<T>(value), *p, *p, *p, *p};
      return *p;
    }
    auto i = pool.size();
    pool.push_back(node_t<T> {std::forward<T>(value), i, i, i, i});
    return i;
  }

  std::optional<node_ref> try_used_space();
  void free(node_ref ref) { deleted_set.push_back({node(ref).a21, ref}); }
  node_t<T>& node(node_ref ref) { return pool[ref]; }
  const node_t<T>& node(node_ref ref) const { return pool[ref]; }
  bool is_leaf(node_ref ref) { return ref == node(ref).a21 && ref == node(ref).a22; }
  void link_parent_child(node_ref, node_ref);
  void link_siblings(node_ref, node_ref);

  std::vector<node_t<T>> pool;
  std::vector<std::pair<node_ref, node_ref>> deleted_set; // [f,l]
};

/*---------- node --------------*/

template <typename T>
struct node_t {
  T value;
  node_ref a11, a12, a21, a22;
  /*    a11 | a12
        ---- ----
        a21 | a22    */
};

/* ------ forest ---------- */

template <typename T>
node_ref forest<T>::add(T value) {
  auto next = next_free(std::move(value));
  node(next).a12 = node_ref(-1); // root's last value
  return next;
}

template <typename T>
node_ref forest<T>::add_child(node_ref ref, T value) {
  // assert ref in [0, pool.size())
  auto next = next_free(std::move(value));
  if (is_leaf(ref)) link_parent_child(ref, next);
  else link_siblings(node(ref).a22, next);
  return next;
}

template <typename T>
node_ref forest<T>::add_sibling(node_ref ref, T value) {
  // assert ref in [0, pool.size())
  auto next = next_free(std::move(value));
  link_siblings(ref, next);
  return next;
}

template <typename T>
node_ref forest<T>::remove(node_ref ref) {
  if (node(ref).a12 == node_ref(-1)) { // root
    free(ref);
    node(ref) = node_t<T> {T(), 0, node_ref(-1), 0, 0};
    return node_ref(-1);
  }
  auto prev = node(ref).a11;
  auto next = node(ref).a12;
  bool is_sibling_left = node(prev).a12 == ref;
  bool is_sibling_right = node(next).a11 == ref;

  if (is_sibling_left) node(prev).a12 = next;
  else node(prev).a21 = next; // parent on the left
  if (is_sibling_right) node(next).a11 = prev;
  else node(next).a22 = prev; // parent on the right
  free(ref);
  return next;
}

template <typename T>
std::optional<node_ref> forest<T>::try_used_space() {
  if (!deleted_set.size()) { return {}; }
  auto& back = deleted_set.back();
  node_ref first(back.first);
  node_ref last(back.second);
  if (first == last) { // just one elem
    deleted_set.pop_back();
    return {first};
  }
  if (!is_leaf(first)) {
    auto next = node(first).a12;
    auto prev = node(first).a22;
    node(next).a11 = prev;
    node(prev).a12 = next;
  }
  back.first = is_leaf(first) ? node(first).a12 : node(first).a21;
  return {first};
}

template <typename T>
void forest<T>::link_parent_child(node_ref parent, node_ref child) {
  node(parent).a21 = child;
  node(parent).a22 = child;
  node(child).a11 = parent;
  node(child).a12 = parent;
}

template <typename T>
void forest<T>::link_siblings(node_ref x, node_ref y) {
  auto next = node(x).a12;
  if (x == node(next).a22) node(next).a22 = y;
  else node(next).a11 = y;
  node(x).a12 = y;
  node(y).a12 = next;
  node(y).a11 = x;
}

/*----------- algorithms  -------- */

/*
  dir:
    down --> pre-order
    up --> post-order
*/
template <typename I, typename Op>
void traverse(I f, I l, direction dir, Op op) {
  while (f != l) {
    if (f.dir() == dir) op(*f);
    ++f;
  }
}

template <typename I, typename Op>
void traverse(I f, I l, Op op) {
  while (f != l) { op(*f); ++f; }
}

template <typename I, typename Op>
void traverse_back(I f, I l, Op op) {
  while (f != l) { --l; op(*l); }
}

/* ------------ forest_iterator --------- */

template <typename T>
struct forest_iterator {
  typedef typename std::iterator_traits<forest_iterator<T>>::pointer pointer;
  typedef typename std::iterator_traits<forest_iterator<T>>::reference reference;
  forest_iterator() = default;
  forest_iterator(const forest_iterator<T>& x) = default;
  forest_iterator<T>& operator=(const forest_iterator<T>& x) = default;
  forest_iterator(forest<T>* f, node_ref ref, node_ref prev)
    : f(f), ref(ref), prev(prev) { }
  forest_iterator& operator++() { next(); return *this; }
  forest_iterator operator++(int) { auto tmp = *this; next(); return tmp; }
  forest_iterator& operator--() { previous(); return *this; }
  forest_iterator operator--(int) { auto tmp = *this; previous(); return tmp; }
  const reference operator*() const { return (*f).node(ref).value; }
  reference operator*() { return (*f).node(ref).value; }
  pointer operator->() const { return &(*f).node(ref).value; }
  void next();
  void previous();
  direction dir() const { return (*f).node(ref).a11 == prev ? down : up; }

  forest<T>* f;
  node_ref ref;
  node_ref prev;
};

template <typename T>
void forest_iterator<T>::next() {
  if ((*f).node(ref).a11 == prev) {
    prev = ref; ref = (*f).node(ref).a21;
  } else {
    prev = ref; ref = (*f).node(ref).a12;
  }
}

template <typename T>
void forest_iterator<T>::previous() {
  if ((*f).node(prev).a21 == ref) {
    ref = prev; prev = (*f).node(prev).a11;
  } else {
    ref = prev; prev = (*f).node(prev).a22;
  }
}

template <typename T>
bool operator==(const forest_iterator<T>& i, const forest_iterator<T>& j) {
  return i.ref == j.ref && i.dir() == j.dir();
}

template <typename T>
bool operator!=(const forest_iterator<T>& i, const forest_iterator<T>& j) {
  return !(i == j);
}

/* ------------ child_iterator --------- */

template <typename T>
struct child_iterator {
  typedef typename std::iterator_traits<child_iterator<T>>::pointer pointer;
  typedef typename std::iterator_traits<child_iterator<T>>::reference reference;
  child_iterator() = default;
  child_iterator(const child_iterator<T>& x) = default;
  child_iterator<T>& operator=(const child_iterator<T>& x) = default;
  child_iterator(forest<T>* f, node_ref ref, node_ref prev) : f(f), ref(ref), prev(prev) {}
  child_iterator& operator++() { next(); return *this; }
  child_iterator operator++(int) { auto tmp = *this; next(); return tmp; }
  child_iterator operator--(int) { auto tmp = *this; previous(); return tmp; }
  child_iterator operator--() { previous(); return *this; }
  const reference operator*() const { return (*f).node(ref).value; }
  reference operator*() { return (*f).node(ref).value; }
  pointer operator->() const { return &(*f).node(ref).value; }
  void next() { prev = ref; ref = (*f).node(ref).a12; }
  void previous() { ref = prev; prev = (*f).node(prev).a11; }

  forest<T> *f;
  node_ref ref;
  node_ref prev;
};

template <typename T>
bool operator==(const child_iterator<T>& i, const child_iterator<T>& j) {
  return i.ref == j.ref;
}

template <typename T>
bool operator!=(const child_iterator<T>& i, const child_iterator<T>& j) {
  return !(i == j);
}

}; // namespace library

template <typename T>
struct std::iterator_traits<library::forest_iterator<T>> {
  typedef std::ptrdiff_t difference_type;
  typedef T value_type;
  typedef T& reference;
  typedef T* pointer;
  typedef std::bidirectional_iterator_tag iterator_category;
};

template <typename T>
struct std::iterator_traits<library::child_iterator<T>> {
  typedef std::ptrdiff_t difference_type;
  typedef T value_type;
  typedef T& reference;
  typedef T* pointer;
  typedef std::bidirectional_iterator_tag iterator_category;
};