struct knoten
{
string zeichenkette;
int knotennummer;
struct knoten *vor;
struct knoten *nach;
struct knoten *nach2;
};

knoten * einlesen()
{
  string temp;
  knoten *sicher;
  knoten *tempit;
  knoten *first;
  int rein = 0;
  int i=-1;

  do
    {
      i++;


      if(i==0)
	{
	  cin >> temp;
   
	  first = new knoten;
	  first->knotennummer = i+1;
	  first->zeichenkette = temp;
	  first->vor = NULL;
	  first->nach = NULL;
	  first->nach2 = NULL;

	}

      sicher = first;



      if(i>0)
	{
	  cin >> temp;
   
	  tempit = new knoten;
	  tempit->knotennummer = i+1;
	  tempit->zeichenkette = temp;
	  tempit->vor = NULL;
   

	  while(rein == 0)
	    {

	      if (temp <= (sicher->zeichenkette))
		{

		  if (sicher->nach == NULL)
		    {
		      sicher->nach = tempit;
		      tempit->vor = sicher;
		      tempit->nach = NULL;
		      tempit->nach2 = NULL;

		    rein = 1;
		      break;
		    }
		  else
		    {
		      sicher = sicher->nach;
		    }
		}
	      if (temp > (sicher->zeichenkette))
		{
  
		  if (sicher->nach2 == NULL)
		    {
		      sicher->nach2 = tempit;
		      tempit->vor = sicher;
		      tempit->nach = NULL;
		      tempit->nach2 = NULL;
		      rein = 1;
		      break;
		    }
		  else {
		    sicher = sicher->nach2;
		  }
		}
            rein = 0;
	    }
	}
    }
  while((temp != "ENDE") && (i != MAXANZAHL-1));


  return first;

}

struct Node
{
   Node() : name(""), prev(0), next(0), last(0), id(0) {}
   string name;
   int id;
   struct Node* prev;
   struct Node* next;
   struct Node* last;
}

Node* Node_pushback(Node* node, const string & name)
{
   Node* ptr = 0;

   ptr = new Node();
   ptr->name = name;
   
   if(node == 0)
   {
      node = ptr;
      node->last = ptr;
   }
   else
   {
      ptr->id = node->last->id + 1;
      node->last->next = ptr;
      ptr->prev = node->last;
      node->last = ptr;
   }  

   return node;
}

void Node_delete(Node* node)
{
   Node* run = 0;
   while(run = node)
   {
      node = node->next;
      delete run;
   }
}

Node* Node_readin()
{
   Node* node = 0;
   string temp = "";
   
   while(1)
   {
       cin >> temp;
       if(temp == "ENDE") break;

       node = Node_pushback(node, temp);
       if(node->last->id == MAXANZAHL-1) break;
   }
   
   return node;
}