Under construction

Still being built. Things may change

Cousin's Aunt

Time limit8sMemory limit512 MB

Summary
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's brother's son.
  • 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 brother is a son of X's father or mother who is not X.
  • X's grandfather is the father of X's father or mother.
  • X's grandson is a son of X's son or daughter.
  • X's uncle is a brother of X's father or mother.
  • X's 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.

  • The distance from X to X's father, mother, son or daughter is one.
  • The distance from X to X's husband or wife is 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 TT (1≤T≤2001 \le T \le 200).

Each of the next TT 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.

Examples2

  1. Example 1

    Input
    7
    C is A's father's brother's son's aunt
    C is A's mother's brother's son's aunt
    C is A's son's mother's mother's son
    C is A's aunt's niece's aunt's niece
    C is A's father's son's brother
    C is A's son's son's mother
    C is A
    
    Expected output
    5 3
    5 1
    2 2
    6 0
    2 0
    1 1
    0 0
    
  2. Example 2

    Input
    16
    C is A's father
    C is A's mother
    C is A's son
    C is A's daughter
    C is A's husband
    C is A's wife
    C is A's brother
    C is A's sister
    C is A's grandfather
    C is A's grandmother
    C is A's grandson
    C is A's granddaughter
    C is A's uncle
    C is A's aunt
    C is A's nephew
    C is A's niece
    
    Expected output
    1 1
    1 1
    1 1
    1 1
    0 0
    0 0
    2 2
    2 2
    2 2
    2 2
    2 2
    2 2
    3 3
    3 3
    3 3
    3 3