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.
Medium5GraphDFSTreeImplementationInterviewNo attempts yetTime limit2sMemory limit512 MBFarmer 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.
The first line of input contains N (1≤N≤100) followed by the names of two cows. Cow names are strings of at most 10 uppercase letters (A…Z). Farmer John is curious about the relationship between the two cows on this line of input.
The next N lines each contain two cow names X and Y, indicating that X is the mother of Y.
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.
SIBLINGS if BESSIE and ELSIE have the same mother.ELSIE is the (relation) of BESSIE, where (relation) is mother one generation up, grand-mother two generations up, great-grand-mother three generations up, and gains one more great- for every further generation.ELSIE is the aunt of BESSIE if ELSIE is a child of BESSIE's grand-mother, ELSIE is the great-aunt of BESSIE if ELSIE is a child of BESSIE's great-grand-mother, ELSIE is the great-great-aunt of BESSIE if ELSIE is a child of BESSIE's great-great-grand-mother, and so on.COUSINS.NOT RELATED if 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.
