Given a chain of up to ten kinship terms describing how C relates to A, report the maximum and minimum possible degree of kinship between A and C.
Hard8GraphShortest pathBrute forceImplementationNo attempts yetTime limit8sMemory limit512 MBSarah likes reading books. One day she wondered about the family in a mystery novel. The story says:
father's brother's son.aunt.Then she asked herself, "so how many degrees of kinship are there between A and C?"
The relation between B and C reads in two ways. C is either the sister of B's father or the sister of B's mother. In the first reading C is the sister of A's father, so C is in the third degree of kinship to A. In the second reading C is the sister of the wife of A's father's brother, so C is in the fifth degree.
You are a friend of Sarah's and you are good at programming. You can help her by writing a program that computes the maximum and the minimum degree of kinship between A and C for a given relation.
The relation between A and C is written as a sequence of these sixteen basic relations: father, mother, son, daughter, husband, wife, brother, sister, grandfather, grandmother, grandson, granddaughter, uncle, aunt, nephew, niece.
The relations mean the following.
brother is a son of X's father or mother who is not X.grandfather is the father of X's father or mother.grandson is a son of X's son or daughter.uncle is a brother of X's father or mother.nephew is a son of X's brother or sister.sister, grandmother, granddaughter, aunt and niece are defined the same way.Assume the family has none of the following: adoption, marriage between relatives (so the family tree has no cycle), divorce, remarriage, bigamy, same-sex marriage.
The degree of kinship is defined as follows.
father, mother, son or daughter is one.husband or wife is zero.The first line has the number of datasets T (1≤T≤200).
Each of the next T lines holds one dataset in this format.
C is A('s relation)*
Here relation is one of the sixteen words listed above. The asterisk means the part inside the parentheses repeats zero or more times. A dataset holds at most ten relations. Every dataset admits at least one family that matches it.
For each dataset, print the maximum and the minimum degree of kinship between A and C on one line, separated by exactly one space. Print no other characters.