Problem Three

Introduction

John is researching the family tree for his pet quesnot Mulder. Quesnots are mythical animals who cooperate to raise a number of young. Adult quesnots form a parenthood of up to ten parents to raise a litter of young. Once the young have matured, all parents are exhausted and cannot help raise a second litter before they die.

John has determined some of Mulder's ancestors' families, but is having trouble determining whether certain relatives are ancestors of another. He has written a program to calculate this fact, but John requires lists of a particular format. Your job is to convert his family tree into one or more lists for him to use.

Input File - three.in

One or more family trees will be given as input. Input will be terminated by end of file.

One family tree consists of at least two lines of input. Except for the final line (consisting of the single word END), each line of one family tree will consist of a quesnot name, followed by a list of its one to ten parents. Each name will be at most 30 characters, and may include letters, numbers, hyphens or periods (but not spaces). Names on a line will be separated by commas. There will be at least one and at most 5000 unique names in the tree, and no quesnot can be his own ancestor. At the end of each family tree will be the word END on a line by itself.

Recall that each quesnot will have at most one child. Brothers and sisters, aunts and uncles will not be included in the input. Each name will occur as the first name on a line at most once. You may assume that the first name on the first line is the bottom of the tree (i.e., will have no children), and that this is the only name in the file with no children.

Sample Input File

Mulder,Bob,Julie
Bob,Adam,Jane
Jane,Monica,George
Julie,Pat
END

Visualization Corresponding to Sample Input File

 Monica  George 
      \  /      
       \/       
Adam  Jane  Pat 
   \   /    /   
    \ /    /    
    Bob  Julie  
      \  /      
       \/       
     Mulder     

Output Requirements - System.out (terminal output)

You are to produce a minimum number of lists with the following properties:

• Every quesnot mentioned in the tree occurs in each list exactly once
• Quesnot A is an ancestor of quesnot B exactly when A appears before B in every list.

The first line of output indicates the number of lists m, m > 0. A blank line then appears. Following are m lists, each containing all names in appropriate order. A blank line appears after each list.

There may be several solutions satisfying these requirements. Any such solution may be chosen.

Sample Output

2

Adam
Monica
George
Jane
Bob
Pat
Julie
Mulder

Pat
Julie
George
Monica
Jane
Adam
Bob
Mulder