#include <string>
#include <map>
#include "infograph.h"

typedef string String;

struct EdgeData{
  bool MinoMark;
  bool ThesMark;
  EdgeData(){
    MinoMark=ThesMark=false;
  }
};

typedef enum {NoMark, MinoMark, Candle} VertMark;
struct VertData{
  VertMark mark;
  String name;
  VertData(String nam=""){
    mark=NoMark;
    name=nam;
  }
};

int main(void){
  InfoGraph<VertData,EdgeData> maze;
  map<String,Vertex,less<String> > Caverns;

  // Read the input and build the maze
  String dummy,SrcName,DstName;
  Vertex SrcVert,DstVert;
  cin>>dummy;
  while(dummy!="END"){
    cin>>SrcName;
    // Does our graph already have a cavern of this name
    if(Caverns.find(SrcName)==Caverns.end()){
      // No, so we need to insert it
      SrcVert=Caverns[SrcName]=maze.InsertVertex(VertData(SrcName));
    }else{
      // Yes, we have it already
      SrcVert=Caverns[SrcName];
    }
    cin>>dummy;
    // Read the forst word after "TO"
    cin>>DstName;
    // Insert edges until we are done with this line of input
    while((DstName!="END")&&(DstName!="FROM")){
      // Does our graph already have a cavern of this name
      if(Caverns.find(DstName)==Caverns.end()){
        // No, so we need to insert it
	DstVert=Caverns[DstName]=maze.InsertVertex(VertData(DstName));
      }else{
        // Yes, we have it already
	DstVert=Caverns[DstName];
      }
      // Insert a tunnel (notice that the order of insertions is
      // such that a traversal of departing edge list gives tunnels
      // in counterclockwise order
      maze.InsertEdge(SrcVert,DstVert,EdgeData());
      // Read the next word from input
      cin>>DstName;
    }
    // Last word we read is "FROM" or "END"
    dummy=DstName;
  }
  // Determine starting positions for our heroes
  cin>>SrcName>>DstName;
  Vertex ThesPos=Caverns[DstName];
  Vertex ThesFrom=Caverns[SrcName];
  cin>>SrcName>>DstName;
  Vertex MinoPos=Caverns[DstName];
  Vertex MinoFrom=Caverns[SrcName];

  Edge exit;
  VertData vd;
  EdgeData ed;
  // Simulate until somebody gets killed
  while(true){

    // Check if there is an encounter in the tunnel
    if(((MinoPos==ThesFrom)&&(ThesPos==MinoFrom))||
       ((MinoPos==ThesPos)&&(MinoFrom==ThesFrom))){
      cout<<"Theseus is killed between "<<maze.VertexInfo(ThesFrom).name
	  <<" and "<<maze.VertexInfo(ThesPos).name<<endl;
      return 0;
    }

    // Check if they are in the same cavern
    if(ThesPos==MinoPos){
      cout<<"The Minotaur is slain in "<<maze.VertexInfo(MinoPos).name<<endl;
      return 0;
    }

    // Find the tunnel Theseus just entered from
    exit=maze.FirstDepartEdge(ThesPos);
    while(maze.Target(exit)!=ThesFrom)
      exit=maze.NextDepartEdge(exit);
    // Was Minotaur in this cavern before?
    if(maze.VertexInfo(ThesPos).mark==NoMark){
      // We are not following the Minotaur. Go right and take
      // the first exit that is not marked with phosphorescent paint
      do{
	exit=maze.NextDepartEdge(exit);
        // We are going arround a cavern, so wrap arround if needed
	if(maze.IsNil(exit))
	  exit=maze.FirstDepartEdge(ThesPos);
      }while(maze.EdgeInfo(exit).ThesMark);
    }else{
      // We are following the Minotaur. Light a candle in this
      // cavern, then go right and take Minotaur's exit
      vd=maze.VertexInfo(ThesPos);
      vd.mark=Candle;
      maze.VertexAssign(ThesPos,vd);
      do{
	exit=maze.NextDepartEdge(exit);
        // We are going arround a cavern, so wrap arround if needed
	if(maze.IsNil(exit))
	  exit=maze.FirstDepartEdge(ThesPos);
      }while(!maze.EdgeInfo(exit).MinoMark);
    }
    // Mark the exit with the phosphorescent paint
    ed=maze.EdgeInfo(exit);
    ed.ThesMark=true;
    maze.EdgeAssign(exit,ed);
    // Update Theseus's position
    ThesFrom=ThesPos;
    ThesPos=maze.Target(exit);

    // Find the exit the Minotaur just entered from
    exit=maze.FirstDepartEdge(MinoPos);
    while(maze.Target(exit)!=MinoFrom)
      exit=maze.NextDepartEdge(exit);
    // Go left and take first exit unmarked by Minotaur
    // (and you don't want to know how the Minotaur marks his exits)
    do{
      exit=maze.PrevDepartEdge(exit);
      // We are going arround a cavern, so wrap arround if needed
      if(maze.IsNil(exit))
	exit=maze.LastDepartEdge(MinoPos);
    }while(maze.EdgeInfo(exit).MinoMark);
    // Mark the exit, you don't want to know how
    EdgeData ed=maze.EdgeInfo(exit);
    ed.MinoMark=true;
    maze.EdgeAssign(exit,ed);
    // Leave scent in the cavern, so that Theseus knows when to follow
    vd=maze.VertexInfo(MinoPos);
    vd.mark=MinoMark;
    maze.VertexAssign(MinoPos,vd);
    // Is that a candle at the end of the tunnel?
    if(maze.VertexInfo(maze.Target(exit)).mark==Candle){
      // Candle burning, run back down the tunnel
      MinoFrom=maze.Target(exit);
    }else{
      // No candle, enter the new cavern
      MinoFrom=MinoPos;
      MinoPos=maze.Target(exit);
    }
  }
}
