Trust groups

The personnel department of 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 the employees in the affected groups and they have detected the root of the problem: trust (or, rather, the lack thereof). Some employees do not trust the rest of the group, and this is decreasing their 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., they are formed by people who trust each other. They have asked the employees, and they know the people each employee trusts directly. Moreover, if employee A trusts employee B and employee B trusts employee C, then employee A will trust employee C. And obviously, each employee trusts himself. They want to create as few groups as possible to reduce administration 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.

Input 

The input consists of several test cases. Each test case begins with a line containing two positive integers P and T ( 1P1000, 0T999000) separated by a single space. P lines come next, each containing the name of one person. The names will 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 will be strings of uppercase or lowercase characters (with no blanks or punctuation marks), with a maximum length of 10 characters. There will not be repetitions in the complete names of the people. After the names there will appear T blocks of 2 lines representing the trust relations between people. Each line of the block will contain the name of a person in the same format as before, and the block will mean that the person in the first line trusts the person in the second line. All people appearing in the confidence relations will have appeared in the previous list of P people.

The input will end with the ``phantom'' test case `0 0', which must not be processed.

Output 

For each test case, the output will be a line containing a positive integer representing the minimum number of stable groups of people that can be formed.

Sample Input 

3 2
McBride, John
Smith, Peter
Brown, Anna
Brown, Anna
Smith, Peter
Smith, Peter
Brown, Anna
3 2
McBride, John
Smith, Peter
Brown, Anna
Brown, Anna
Smith, Peter
McBride, John
Smith, Peter
0 0

Sample Output 

2
3

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define maxN 1005
using namespace std;
vector<int> g[maxN];
int vfind[maxN], findIdx;
int stk[maxN], stkIdx;
int in_stk[maxN], visited[maxN];
int scc_cnt;
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(!visited[*it])
            mn = min(mn, scc(*it));
        if(in_stk[*it])
            mn = min(mn, vfind[*it]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
        } while(stk[stkIdx--] != nd);
        scc_cnt++;
    }
    return mn;
}
int main() {
    int n, m, x, y, i;
    char name[50], a[50], b[50];
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0 && m == 0)
            break;
        map<string, int> mapped;
        getchar();
        for(i = 0; i < n; i++) {
            gets(name);
            mapped[name] = i;
            g[i].clear();
            visited[i] = in_stk[i] = 0;
        }
        for(i = 0; i < m; i++) {
            gets(a);
            gets(b);
            x = mapped[a];
            y = mapped[b];
            g[x].push_back(y);
        }
        scc_cnt = 0;
        for(i = 0; i < n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        printf("%d\n", scc_cnt);
    }
    return 0;
}