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

using namespace std;

struct node
{ string data;
  node * left, * right;

  node(string d)
  { data = d;
    left = NULL;
    right = NULL; } };

class AR
{ public:
    node * t;
    int where;
        
    AR(node * init_t, int init_where = 1)
    { t = init_t;
      where = init_where; } };

class stack: public vector <AR *>
{ public:

    void push(AR * a)
    { push_back(a); }

    AR * pop()
    { AR * result = back();
      pop_back();
      return result; }

    AR * top() const
    { return back(); }

    bool not_empty() const
    { return size() > 0; } };

class tree
{ protected:
    node * root;

  public:
    tree()
    { root = NULL; }

    void add(node * & t, string s)
    { if (t == NULL)
        t = new node(s);
      else if (s < t->data)
        add(t->left, s);
      else
        add(t->right, s); }

    void add(string s)
    { add(root, s); }

    stack nr_start_run()
    { stack S;
      S.push(new AR(root));
      return S; }

    string nr_run(stack & S)
    { while (S.not_empty())
      { AR & top = * S.top();

        if (top.where == 1)
        { if (top.t == NULL)
          { S.pop();
            continue; }
          S.push(new AR(top.t->left));
          top.where = 2;
          continue; }

        else if (top.where == 2)
        { S.push(new AR(top.t->right));
          top.where = 3;
          return top.t->data; }

        else if (top.where == 3)
        { S.pop();
          continue; } }
          
      return "***end***"; } };

int main()
{ tree t1;
  t1.add("egg"); t1.add("pig"); t1.add("dog"); t1.add("nut"); t1.add("ant");
  t1.add("jug"); t1.add("qat"); t1.add("rat"); t1.add("bat"); t1.add("git");
  t1.add("map"); t1.add("kit"); t1.add("ink"); t1.add("sud"); t1.add("log");
  t1.add("hat"); t1.add("cat"); t1.add("old"); t1.add("fig"); t1.add("tip");

  tree t2;
  t2.add("qat"); t2.add("dog"); t2.add("log"); t2.add("fig"); t2.add("hat");
  t2.add("ink"); t2.add("egg"); t2.add("rat"); t2.add("cat"); t2.add("kit");
  t2.add("tip"); t2.add("git"); t2.add("jug"); t2.add("sud"); t2.add("bat");
  t2.add("ant"); t2.add("old"); t2.add("pig"); t2.add("nut"); t2.add("map");

  stack s1 = t2.nr_start_run();
  stack s2 = t2.nr_start_run();

  while (true)
  { string x1 = t1.nr_run(s1);
    string x2 = t2.nr_run(s2);
    cout << x1 << " " << x2 << "\n";
    if (x1 != x2)
    { cout << "Different\n";
      break; }
    if (x1 == "***end***")
    { cout << "Same\n";
      break; } } }