#include <iostream>
#include <iomanip>
#include <vector>
#include <deque>
#include <string>

class node
{ protected:
    string str;
    vector <node *> links;

  public:
    node(string s)
    { str = s; }

    static node * mk(string s)
    { return new node(s); }

    node * add(node * n)
    { links.push_back(n);
      return this; }

    string getname()
    { return str; }

    int getnumlinks()
    { return links.size(); }

    node * getlink(int i)
    { return links[i]; }
};

/*
   void print(node * n, int depth = 0)
   { <<< THIS IS POSITION 0 >>>
      cout << setw(depth * 7) << " " << n->getname() << "\n";

      int num = n->getnumlinks();

      for (int i = 0; i < num; i += 1)
      { 
         print(n->getlink(i), depth+1);
         <<< THIS IS POSITION 1 >>>
      }
   }
*/

struct AR  // the Activation Record or Stack Frame
{ int position;
  node * n;
  int depth;
  int num;
  int i;

  AR(int pos, node * n0, int d)
  { position = pos;
    n = n0;
    depth = d;
    num = 0;
    i = 0; }
};

void waitforme();
void printqueue(deque <AR *> q);

void print(node * n)
{
   deque <AR *> queue;
   queue.push_back(new AR(0, n, 0));

   while ( ! queue.empty())
   {  waitforme();
      printqueue(queue);

      AR * current = queue.front();

      if (current->position == 0)
      {
         cout << setw(current->depth * 7) << " " << current->n->getname() << "\n";

         current->num = current->n->getnumlinks();

         current->i = 0;
         if (current->i < current->num)
         {
            queue.push_back(new AR(0, current->n->getlink(current->i), current->depth + 1));
            current->position = 1;
         }
         else
         {
            delete current;
            queue.pop_front();
         }
      }

      else if (current->position == 1)
      {
         current->i += 1;

         if (current->i < current->num)
         {
            queue.push_back(new AR(0, current->n->getlink(current->i), current->depth + 1));
            current->position = 1;
         }
         else
         {
            delete current;
            queue.pop_front();
         }
      }
   }
}

void main()
{ node * t1 = node::mk("ant")
                             ->add(node::mk("bat")
                                                  ->add(node::mk("egg")
                                                                       ->add(node::mk("kit"))
                                                                       ->add(node::mk("log")))
                                                  ->add(node::mk("fig"))
                                                  ->add(node::mk("gat")
                                                                       ->add(node::mk("map"))
                                                                       ->add(node::mk("nut"))
                                                                       ->add(node::mk("old"))
                                                                       ->add(node::mk("pig"))))
                             ->add(node::mk("cat")
                                                  ->add(node::mk("hat")))
                             ->add(node::mk("dog")
                                                  ->add(node::mk("ink")
                                                                       ->add(node::mk("qat"))
                                                                       ->add(node::mk("rat")))
                                                  ->add(node::mk("jug")
                                                                       ->add(node::mk("sud"))
                                                                       ->add(node::mk("tip"))));
  print(t1); }

void printqueue(deque <AR *> q)
{ int num = q.size();
  cout << "\n";
  cout << "pos:   ";
  for (int i = 0; i < num; i += 1)
    cout << setw(7) << q[i]->position;
  cout << "\n";
  cout << "n:     ";
  for (int i = 0; i < num; i += 1)
    cout << setw(7) << q[i]->n->getname();
  cout << "\n";
  cout << "depth: ";
  for (int i = 0; i < num; i += 1)
    cout << setw(7) << q[i]->depth;
  cout << "\n";
  cout << "num:   ";
  for (int i = 0; i < num; i += 1)
    cout << setw(7) << q[i]->num;
  cout << "\n";
  cout << "i:     ";
  for (int i = 0; i < num; i += 1)
    cout << setw(7) << q[i]->i;
  cout << "\n\n"; }

void waitforme()
{ string xxx;
  getline(cin, xxx); }