Cousin's Aunt
Time limit8sMemory limit512 MB
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.
- Level
Hard8 of 10
- Topics
- Graph, Shortest path, Brute force, Implementation
- Solved
- No attempts yet
Problem
Sarah likes reading books. One day she wondered about the family in a mystery novel. The story says:
- B is A's
father'sbrother'sson. - C is B's
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.
- X's
brotheris asonof X'sfatherormotherwho is not X. - X's
grandfatheris thefatherof X'sfatherormother. - X's
grandsonis asonof X'ssonordaughter. - X's
uncleis abrotherof X'sfatherormother. - X's
nephewis asonof X'sbrotherorsister. sister,grandmother,granddaughter,auntandnieceare 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.
- The distance from X to X's
father,mother,sonordaughteris one. - The distance from X to X's
husbandorwifeis zero. - The degree of kinship between X and Y is the shortest distance from X to Y that the rules above give.
Input
The first line has the number of datasets ().
Each of the next 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.
Output
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.