Family Tree

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 MB

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 NN (1N1001 \leq N \leq 100) followed by the names of two cows. Cow names are strings of at most 10 uppercase letters (AZA \ldots Z). Farmer John is curious about the relationship between the two cows on this line of input.

The next NN lines each contain two cow names XX and YY, indicating that XX is the mother of YY.

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 SIBLINGS if 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) 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.
  • 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 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.
  • 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 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.