Family Tree
InterviewTime limit2sMemory limit512 MB
Given a set of mother-child pairs, classify the relationship between two cows as siblings, direct ancestor, aunt, cousins, or unrelated, following a fixed rule order.
- Level
Medium5 of 10
- Topics
- Graph, DFS, Tree, Implementation
- Solved
- No attempts yet
Problem
Farmer John runs a family farm that has been handed down over several generations, and his herd of cows traces back through several generations on the same farm. Going through the old records, Farmer John became curious about how the cows in his current herd are related to each other. Help him work out the relationship between two of them.
Input
The first line of input contains () followed by the names of two cows. Cow names are strings of at most 10 uppercase letters (). Farmer John is curious about the relationship between the two cows on this line of input.
The next lines each contain two cow names and , indicating that is the mother of .
Output
Print one line describing the relationship between the two cows named on the first line. In the descriptions below, call those two cows BESSIE and ELSIE. Apply only the first rule in this list that matches.
- Print
SIBLINGSif BESSIE and ELSIE have the same mother. - BESSIE might be a direct descendant of ELSIE, meaning that ELSIE is the mother, grand-mother, great-grand-mother, great-great-grand-mother, and so on, of BESSIE. In that case print
ELSIE is the (relation) of BESSIE, where (relation) ismotherone generation up,grand-mothertwo generations up,great-grand-motherthree generations up, and gains one moregreat-for every further generation. - If ELSIE is a child of an ancestor of BESSIE, and ELSIE is herself neither an ancestor nor a sister of BESSIE, then ELSIE is the aunt of BESSIE. Print
ELSIE is the aunt of BESSIEif ELSIE is a child of BESSIE's grand-mother,ELSIE is the great-aunt of BESSIEif ELSIE is a child of BESSIE's great-grand-mother,ELSIE is the great-great-aunt of BESSIEif ELSIE is a child of BESSIE's great-great-grand-mother, and so on. - If the two cows are related in any other way, that is, they share a common ancestor, they are cousins, and you print
COUSINS. - Print
NOT RELATEDif BESSIE and ELSIE have no common ancestor and neither is a direct descendant of the other.
The diagram below collects the relationships above. They are the only relationship types this problem asks about. A relationship such as niece (the daughter of a sister) is not needed, because if BESSIE is the niece of ELSIE, then ELSIE is the aunt of BESSIE.
