16852번 - Junior 다국어

In many cultures, children share their last name with at least one of their parents. In addition, in quite a few families, children will also be given a middle name to honor an ancestor, often a grandparent or parent. And in some cases, parents go even further, and name a child after their own first name. Most often, this is firstborn sons named after their father, and in that case, the word “junior” is often appended to the name to distinguish them. In this problem, you will use these naming conventions to determine how many families seem to be contained in a data set.

You will be given a list of names. Each name is a string containing only lowercase letters and whitespace (which separates parts of the name). Names consist of a first name (always), a middle name (optional), a last name (always), and one of the words “junior” or “iii” (optional). No one will ever have a first, middle, or last name of “junior” or “iii”. You can infer that person A is the child of person B if (1) person A was born after person B, and (2) one of the following happens:

• Person A has the exact same name as person B, but with “junior” appended.
• Person A has the same name as person B, but with “junior” replaced with “iii”. (That is, B’s name ends in “junior”, and A’s in “iii”, but apart from that replacement, their names are exactly the same.)
• A and B have the same last name, and the middle name of A is the first name of B, and A does not have any “junior” or “iii” appended to his name.

The number of families in your data set is the number of people for whom you cannot find a potential parent in the data set. (Notice that this means that if you have two “fitzgerald kennedy” and one “john fitzgerald kennedy”, it doesn’t matter that you cannot figure out which family he belongs with.)

The first line contains a number K ≥ 1, which is the number of input data sets in the file. This is followed by K data sets of the following form:

The first line of a data set contains a single integer 1 ≤ n ≤ 1000, the number of people in your data set. This is followed by n lines, each containing a string of length at most 80 characters, consisting only of lower-case letters and whitespace. The names will be given in increasing order of when the people were born.

For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then, output the number of families represented in the data set, i.e., the number of people whose parent is not known to be in the data set.

Each data set should be followed by a blank line.