/* Problem 5--Kissin' Cousins
   This was probably the hardest one of the bunch.  There was an
   observation that made it easier:  If you think of descendant-p as
   cousin-(-1)-p, you could use the same formula for everything without
   having to worry about a special case.  Also, since no upper limit was
   given for the number of relatives, this had to be handled
   dynamically. */

#include <fstream>
#include <cstring>
using namespace std;

#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

ifstream in ("prob5.in");
ofstream out ("prob5.out");

class relationship;

class relationship { //Class for the linked list of names
 public :
  char names[2][6]; //Two names
  int r; //The relationship
  relationship *next; //The next relationship in the list
  relationship (char *a, char *b, int r);
  ~relationship ();
};

int main (int argc, char **argv);
void AddRelationship (relationship *&head, char *a, char *b, int r);
relationship * ScanList (relationship *head, char *a);
void GetAncestors (char *a, int p, relationship *&AncList);
void GetRelationship (char *a, char *b, int &m, int &n);

relationship *RList = NULL; //Master list of relationships

/* Relationship constructor function */

relationship::relationship (char *a, char *b, int r) {

 strcpy (names[0],a); //Add information to the node
 strcpy (names[1],b);
 this->r = r;
}

/* Relationship destructor function */

relationship::~relationship () {

 if (next != NULL) delete next; //Deallocate every node in list
}

int main (int argc, char **argv) {

 char command, line[81], a[6],b[6];
 int r;
 while (true) {
  in.get(command); //Get the one character command
  switch (command) {
   case 'E' : return 0; //Exit program
   case '#' : in.getline (line, sizeof line); break;
              //This is a comment; ignore line
   case 'R' : in.get(a,sizeof a); in.get(b,sizeof b);
              in >> r; //Get names, relationships, add them
              AddRelationship (RList,a,b,r);
              in.getline (line, sizeof line); break;
   case 'F' : int m,n; //Get names, compute relationship
              in.get(a,sizeof a); in.get(b,sizeof b);
              GetRelationship (a,b,m,n);
              out << a << " and " << b << " are ";
              switch (m) {
               case -2 : out << "not related." << endl;break;
               case -1 : out << "descendant-" << n << "." << endl;break;
               default : out << "cousin-" << m << "-" << n << "." <<
                         endl;
              }
              in.getline (line, sizeof line); break;
  }
 }
 delete RList; //Deallocate linked list
 return 0;
}

/* AddRelationship simply pushes the new relationship onto the linked
   list, as a stack. */

void AddRelationship (relationship *&head, char *a, char *b, int r) {

 relationship *rel = new relationship (a,b,r);
 rel->next = head;
 head = rel;
}

/* ScanList scans the linked list for a particular name, returning NULL
   if the name isn't there. */

relationship * ScanList (relationship *head, char *a) {

 if (head==NULL || strcmp (a,head->names[0])==0) return head;
 return ScanList (head->next,a);
}

/* GetAncestors builds a linked list of all the ancestors of a given
   person.  a is the person, p is the relationship to the base person,
   AncList is the list. */

void GetAncestors (char *a, int p, relationship *&AncList) {

 AddRelationship (AncList,a,"",p); //A person is his own ancestor.
 for (relationship *P = RList; P != NULL; P = P->next)
  //Go through list, find an ancestor for this person and make sure
  //this person hasn't already been added.
  if (strcmp (P->names[0],a)==0 && ScanList(AncList,P->names[1])==NULL)
   //Recursively get this guy's ancestors.
   GetAncestors (P->names[1],p+P->r,AncList);
}

/* GetRelationship computes the relationship between two individuals.
   m and n are as defined in the problem.  However, if m=-1, it's a
   descendant relationship.  If m=-2, there is no relationship. */

void GetRelationship (char *a, char *b, int &m, int &n) {

 m = -2;
 relationship *AncA = NULL;
 GetAncestors (a,0,AncA); //Get all of a's ancestors.
 relationship *AncB = NULL;
 GetAncestors (b,0,AncB); //Get all of b's ancestors.
 for (relationship *P = AncA; P != NULL; P = P->next) {
  //Go through all of a's ancestors and see if b shares that ancestor.
  relationship *Q = ScanList (AncB,P->names[0]);
  if (Q==NULL) continue; //If not, skip over this guy
  int tm = MIN (P->r, Q->r)-1, //m is the smallest distance to the
                               //common ancestor.
      tn = MAX(P->r,Q->r)-tm-1;//n is the difference in the lengths of
                               //the paths.
  if (m==-2 || tm < m || tm==m && tn < n) { //If this one is closer,
   m = tm; n = tn;}                         //remember it.
 }
}