Genealogical Research

Time Limit:  1 s      Memory Limit:   128 MB
Submission:0     AC:0     Score:100.00


These days, everyone seems to be exploring their ancestry. This effort is supported by family history software, now marketed by a number of vendors. Unfortunately this software is expensive and runs only on the McDoze X operating system. You are to write an open-source equivalent.

Your program accepts a series of commands, one per line. The commands are described by the following syntax:

   command ::= birth
           ::= death
           ::= ancestors
           ::= descendants 
           ::= QUIT
   birth ::= BIRTH child: date: mother: father

   death ::= DEATH person: date

   ancestors ::= ANCESTORS person

   descendants ::= DESCENDANTS person
   child ::= name

   mother ::= name

   father ::= name

   person ::= name

   date ::= name

   name ::= <<any sequence of characters not beginning or ending
with a space or containing a colon>>

Spaces in the input are ignored except where they appear within


. The BIRTH and DEATH commands record the birth and death of an individual. You may assume that each individual has a unique name. The ANCESTORS and DESCENDANTS commands are queries: they print a family tree or a reverse family tree for the named person, using the BIRTH and DEATH information entered by previous commands. The QUIT command indicates the end of input.

The BIRTH, DEATH, and QUIT commands have no output. For each ANCESTORS (DESCENDANTS) command, print the following information:

Leave an empty line between the output sequences for successive commands.

You may assume that no input line exceeds 100 characters, and that there are not more than 250 lines of input. You may assume that DEATH, ANCESTORS, and DESCENDANTS commands refer to a name for which a BIRTH command has previously been given. QUIT appears only as the last line of input.


BIRTH John Doe : January 7, 1599 : Jane Doe : Adam Doe BIRTH Mary Worth : May 18, 1666 : Jane Doe : Adam Doe BIRTH Casper Ghost : Jan 2, 1959 : Mary Worth : John Doe DEATH Mary Worth : Jan 3, 1959 ANCESTORS Casper Ghost DESCENDANTS John Doe QUIT
ANCESTORS of Casper Ghost John Doe January 7, 1599 - Adam Doe Jane Doe Mary Worth May 18, 1666 - Jan 3, 1959 Adam Doe Jane Doe DESCENDANTS of John Doe Casper Ghost Jan 2, 1959 -