Trust groups#6921
The personnel department of the Association of Cookie Monsters (ACM) has noticed that the productivity of various work groups in the company is not as good as it could be. They have interviewed employees in the affected groups and have detected the root of the problem: trust (or, rather, the lack thereof). Some employees do not trust the rest of their group, leading to decreased motivation and happiness. The personnel department wants to solve this problem and has decided to reorganize the groups so that they are stable, i.e., formed by people who trust each other. They have asked the employees, and now know the people each employee directly trusts. Moreover, if employee A trusts employee B, and employee B trusts employee C, then employee A will trust employee C. Obviously, each employee trusts themselves. They want to create as few groups as possible to reduce administrative overhead (they also do not want to work too hard).
With this information, they have contacted you and asked you to write a program that finds the minimum number of stable groups that can be created.
The input consists of multiple test cases. Each test case begins with a line containing two positive integers and (1 \leq P \leq 1000, 0 \leq T \leq 999000), separated by a single space. The following lines each contain the name of one person. Names have the following format: surname, a comma, a space, and first name (for example, McBride, John or Smith, Peter). Both the surname and the first name are strings of uppercase or lowercase characters (with no blanks or punctuation marks), with a maximum length of characters. There will be no repeated full names. After the names, there will be blocks, each consisting of lines, representing trust relations between people. Each line of a block contains the name of a person in the same format as before. The block means that the person in the first line trusts the person in the second line. All people appearing in the trust relations have appeared in the previous list of people.
The input ends with a "phantom" test case , which must not be processed.
For each test case, output a line containing a positive integer representing the minimum number of stable groups of people that can be formed.
Example 1