In computational complexity theory, polynomial-time reduction is an important concept.

If the existence of a polynomial-time algorithm for problem B implies that problem A also has a polynomial-time algorithm, we say that problem A has a polynomial-time reduction to problem B . The relation of reduction is transitive, i.e. if A has a reduction to B and B has a reduction to C , then A has a reduction to C .

Theoretical computer science researchers have found hundreds of polynomial-time reductions between problems, which build a large network of reductions in computational complexity theory.

In this network, some reductions are explicitly presented and others exist implicitly. For example, if the reductions from A to B and from B to C are explicitly presented and the reduction from A to C is not explicitly presented, we say that the reduction from A to C exists implicitly.

In fact, some reductions are not necessary to present explicitly in the network. For example, if reductions from A to B and from B to C exist explicitly or implicitly in the network, then the reduction from A to C is not necessary to present explicitly. By this fact, it's possible to simplify the network of reductions.

Your task is just to simplify the network of reductions such that the number of reductions explicitly presented in the simplified network is minimized and reduction from problem A to problem B exists explicitly or implicitly in the simplified network if and only if it exists in the original network explicitly or implicitly.

Input 

The input consists of multiple test cases. Each test case starts with a line containing two integers N and M (1N100, 0M10000) , which are the number of problems and the number of explicitly presented reductions in the network. The problems are numbered from 1 to N .

Each of the following M lines contains two integers A and B (1AN, 1BN, A B) , which means a polynomial-time reduction from problem A to problem B is explicitly presented in the network. The last test case is followed by a line containing two zeros.

Output 

For each test case, print a line containing the test case number (beginning with 1) followed by a integer which is the number of explicitly presented reductions in the simplified network.

Sample Input 

3 3 
1 2 
2 3 
1 3 
4 6 
1 2 
2 1 
2 3 
3 2 
3 4 
4 3 
0 0

Sample Output 

Case 1: 2 
Case 2: 4

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
vector<int> g[105], vg[105], ng[105];
int vfind[105], findIdx;
int stk[105], stkIdx;
int in_stk[105], visited[105];
int contract[105];
//
int ret;
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd], i;
    for(i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
    	int cnt = 0;
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
            cnt++;
        } while(stk[stkIdx--] != nd);
        if(cnt != 1)	ret += cnt;
    }
    return mn;
} 
int main() {
	int cases = 0;
	int n, m;
	int i, j, k, x, y;
	while(scanf("%d %d", &n, &m) == 2 && n+m) {
		for(i = 1; i <= n; i++)
			g[i].clear();	
		for(i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			g[x].push_back(y);
		}
		ret = 0;// answer.
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        for(i = 1; i <= n; i++) {
        	if(visited[i] == 0) {
        		findIdx = stkIdx = 0;
        		scc(i);
        	}
        }
        int tr[105][105] = {};// transitive graph
        for(i = 1; i <= n; i++) {// new DAG
        	x = contract[i];
        	for(j = 0; j < g[i].size(); j++) {
        		y = contract[g[i][j]];
        		if(x != y)
        			tr[x][y] = 1;
        	}
        }
        // floyd
        for(k = 1; k <= n; k++) {
        	for(i = 1; i <= n; i++) {
        		for(j = 1; j <= n; j++)
        			tr[i][j] |= tr[i][k]&tr[k][j];
        	}
        }
        // count necessary edge
        for(i = 1; i <= n; i++) {
        	for(j = 1; j <= n; j++) {
        		if(i == j) 	continue;
        		if(tr[i][j])  {
        			int necessary = 1;
        			for(k = 1; k <= n; k++) {
        				if(k == i || k == j)
        					continue;
        				if(tr[i][k] && tr[k][j]) 
        					necessary = 0, k = n+1;
        			}
        			ret += necessary;
        		}
        	}
        }
        printf("Case %d: %d\n", ++cases, ret);
	}
	return 0;
}