SimSet begin
  boolean Debugging = true;


  class BinTreeNode(Key);
    value Key;
    text Key;
  virtual: procedure DumpData;
  begin
    ref(BinTreeNode) Left, Right;

    procedure Dump(L);
      integer L;
    begin
      integer I;

      if Right =/= none then Right.Dump(L+1);
      for I := 0 step 1 until L do OutChar('.');
      OutText("Key=" & Key & ":");  DumpData;  OutImage;
      if Left =/= none then Left.Dump(L+1);
    end Dump;

    procedure DumpData;;

    ref(BinTreeNode) procedure Find(K);
      text K;
    begin
      if Key = K then begin
	Find :- this BinTreeNode;
      end else
      if K<Key and Left=/=none then begin
	Find :- Left.Find(K);
      end else
      if K>Key and Right=/=none then begin
	Find :- Right.Find(K);
      end if;
    end Find;

    ref(BinTreeNode) procedure Into(P);
      name P;
      ref(BinTreeNode) P;
    begin
      if P == none then begin
	Into :- P :- this BinTreeNode;
      end else
      if Key = P.Key then begin
	Into :- P;
      end else
      if Key < P.Key then begin
	Into :- Into(P.Left);
      end else begin
	Into :- Into(P.Right);
      end if;
    end Into;
  end BinTreeNode;


  Link class Relation(P, Steps);
    ref(Person) P;
    integer     Steps;
  begin
  end Relation;


  BinTreeNode class Person;
  begin
    ref(Head) Ancestors;

    procedure AddAncestor(P, L);
      ref(Person) P;
      integer     L;
    begin
      new Relation(P,L).Into(Ancestors);
    end AddAncestor;

    procedure DumpData;
    begin
      ref(Relation) Rx;

      Rx :- Ancestors.First;
      while Rx =/= none do begin
	OutText(" (" & Rx.P.Key & ",");  OutInt(Rx.Steps,0);  OutText(")");
	Rx :- Rx.Suc;
      end while;
    end DumpData;

    boolean procedure IsDescendant(P);
      ref(Person) P;
    begin
      comment Is `this Person' a descendant of `P'? ;

      ref(Relation) Rx;
      boolean       IsD;

      if P =/= this Person then begin
	Rx :- Ancestors.First;
	while Rx=/=none and not IsD do begin
	  if Rx.P.IsDescendant(P) then IsDescendant := IsD := true;
	  Rx :- Rx.Suc;
	end while;
      end else IsDescendant := IsD := true;

      if Debugging then begin
	OutText("Debugging: " & Key & " is ");
	if not IsD then OutText("not ");
	OutText("a descendant of " & P.Key);  OutImage;
      end if;
    end IsDescendant;

    integer procedure Level(Px);
      ref(Person) Px;
    begin
      comment How many levels must we go back to get to `Px' (whom we know
       --"--  is an ancestor)? If several paths, choose the shortes. ;

      ref(Relation) Rx;
      integer       Lmin, Lx;

      if Px =/= this Person then begin
	Rx :- Ancestors.First;  Lmin := -1;
	while Rx =/= none do begin
	  Lx := Rx.P.Level(Px);
	  if Lx >= 0 then begin
	    if Debugging then begin
	      OutText("Debug> There are ");  OutInt(Lx, 0);  OutText("+");
	      OutInt(Rx.Steps, 0);  OutText(" = ");  OutInt(Lx + Rx.Steps, 0);
	      OutText(" generations from " & Key & " via " & Rx.P.Key);
	      OutText(" to " & Px.Key);  OutImage;
	    end if;

	    Lx := Lx + Rx.Steps;
	    if Lmin<0 or Lx<Lmin then Lmin := Lx;
	  end if;

	  Rx :- Rx.Suc;
	end while;
      end;

      Level := Lmin;
    end Level;

    Ancestors :- new Head;
  end Person;


  class PersonalRel;
  virtual: procedure Print;
  begin
    procedure Print(F);
      ref(OutFile) F;
    begin
      F.OutText("not related.");
    end Print;
  end PersonalRel;


  PersonalRel class AncestorRel(Level);
    integer Level;
  begin
    procedure Print(F);
      ref(OutFile) F;
    begin
      F.OutText("descendant-");  F.OutInt(Level, 0);  F.OutText(".");
    end Print;

    if Level < 0 then Level := -Level;
  end AncestorRel;


  PersonalRel class CousinRel(Level, Removed, Common);
    ref(Person) Common;
    integer     Level, Removed;
  begin
    boolean procedure BetterThan(CR);
      ref(CousinRel) CR;
    begin
      BetterThan := if Level<CR.Level then true else
                    if Level>CR.Level then false else Removed<CR.Removed;
    end BetterThan;

    procedure Print(F);
      ref(OutFile) F;
    begin
      F.OutText("cousin-");  F.OutInt(Level,   0);
      F.OutText("-");        F.OutInt(Removed, 0);  F.OutText(".");
    end Print;
  end CousinRel;


  ref(PersonalRel) procedure FindCousins(P1, P2);
    ref(Person) P1, P2;
  begin
    ref(PersonalRel) procedure CheckCousins(X1, X2);
      ref(Person) X1, X2;
    begin
      comment Check whether `X1' and `X2' are cousins, by looking at the
       --"--  ancestors of `X1'. ;

      ref(CousinRel) Xx, Xbest;
      ref(Relation)  Rx;

      if X1 =/= X2 then begin
	Rx :- X1.Ancestors.First;  
	while Rx =/= none do begin
	  if X2.IsDescendant(Rx.P) then begin
	    integer L1, L2;

	    L1 := X1.Level(Rx.P);  L2 := X2.Level(Rx.P);
	    Xx :- new CousinRel(Min(L1,L2)-1, Abs(L1-L2), Rx.P);
	  end else begin
	    Xx :- CheckCousins(Rx.P,X2);
	    if Xx =/= none then begin
	      Xx.Level := Xx.Level+Rx.Steps;
	      Xx.Removed := Abs(X1.Level(Xx.Common)-X2.Level(Xx.Common));
	    end if;
	  end if;

	  if Xx =/= none then begin
	    if Xbest==none or else Xx.BetterThan(Xbest) then Xbest :- Xx;
	  end if;
	  Rx :- Rx.Suc;
	end while;
      end;

      CheckCousins :- Xbest;
    end CheckCousins;

    if P1=/=none and P2=/=none then begin
      if P1.IsDescendant(P2) then begin
	FindCousins :- new AncestorRel(P1.Level(P2));
      end else
      if P2.IsDescendant(P1) then begin
	FindCousins :- new AncestorRel(P2.Level(P1));
      end else begin
	ref(CousinRel) R1, R2;

	R1 :- CheckCousins(P1, P2);
	R2 :- CheckCousins(P2, P1);

	if R1 == none and R2 == none then FindCousins :- new PersonalRel else
	if R2 == none then FindCousins :- R1 else
	if R1 == none then FindCousins :- R2 else
	  FindCousins :- if R1.BetterThan(R2) then R1 else R2;
      end if;
    end else FindCousins :- new PersonalRel;
  end FindCousins;


  ref(Person)  Root;


  inspect new InFile("cousins.in") do begin
    ref(OutFile) OutF;
    character    C;

    Open(Blanks(256));
    OutF :- new OutFile("cousins.out");  OutF.Open(Blanks(80));

    InImage;	C := InChar;
    while C <> 'E' do begin
      if Debugging then begin
	OutText("Debug: Read a ");  OutChar(C);  
	OutText("-line: " & Image.Strip);  OutImage;
      end if;

      if C = '#' then begin
      end else
      if C = 'R' then begin
	ref(Person) P1, P2;
	text        N1, N2;
	integer     Lev;
	
	N1 :- Image.Sub(2,5);  N2 :- Image.Sub(7,5);
	SetPos(12);  Lev := InInt;
	
	P1 :- new Person(N1).Into(Root);
	P2 :- new Person(N2).Into(Root);
	P1.AddAncestor(P2, Lev);  
	if Debugging then begin
	  OutText("Dump: Family tree:");  OutImage;
	  Root.Dump(0);
	end if;
      end else begin
	ref(Person) P1, P2;
	text        N1, N2;
	
	N1 :- Image.Sub(2,5);  N2 :- Image.Sub(7,5);
	if Root =/= none then begin
	  P1 :- Root.Find(N1);  P2 :- Root.Find(N2);
	end if;

	OutF.OutText(N1 & " and " & N2 & " are ");
	FindCousins(P1,P2).Print(OutF);
	OutF.OutImage;
      end if;
      
      InImage;  C := InChar;
    end while;

    OutF.Close;  Close;
  end inspect;
end