#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
const long double eps = 1e-12;
double PI = 3.14159265359;
#define readFile freopen("input","r",stdin)
#define writeFile freopen("output","w",stdout)
#define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef pair<int,int> ii;
typedef unsigned long long ULL;
const int INF = 1e8;
const int N=1001,M=2001;
vector<vector<int> > G,dag,bip;
int root[N],rnk[N],V[N],match[M],V2[M],disc[N],low[N],stm[N],t,n,m,v1,v2,res,pntr;
stack<int> st;
vector<ii> E;
vector<int> ver;
inline void init(){for(int i=1;i<=n;i++)root[i]=i,rnk[i]=0;}
int find(int x){return x==root[x]?x:root[x]=find(root[x]);}
inline void merge(int a,int b){
    a = find(a);
    b = find(b);
    if (a==b) return;
    if (rnk[a]<rnk[b]) swap(a,b);
    if (rnk[a]==rnk[b]) rnk[a]++;
    root[b]=a;
}

void dfs(int u){
    V[u] = 1;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if (!V[v]) dfs(v);
    }
    st.push(u);
}

int aug(int u){
    if (V2[u]) return 0;
    V2[u] = 1;
    for(int i=0;i<bip[u].size();i++){
        int v = bip[u][i];
        if (!match[v]||aug(match[v])){
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

void dfs4(int u,int ss){
    V[u] = 1;
    for(int i=0;i<dag[u].size();i++){
        int v = dag[u][i];
        if (V[v]) continue;
        dfs4(v,ss);
        if (ss!=v)
            bip[ss].push_back(ver.size()+v);
    }
}

void tarjan(int u){
    disc[u] = low[u] = pntr++;
    stm[u] = 1;
    st.push(u);
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if (!disc[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else{
            if (stm[v]) low[u] = min(low[u],disc[v]);
        }
    }
    if (low[u]==disc[u]){
        while (st.top()!=u){
            merge(u,st.top());
            stm[st.top()] = 0;
            st.pop();
        }
        stm[st.top()] = 0;
        st.pop();
    }
}


int main(){
#ifndef ONLINE_JUDGE
    readFile;
//    writeFile;
#endif
    fastIO;
    scanf("%d",&t);
    for(int t1=1;t1<=t;t1++){
        scanf("%d%d",&n,&m);
        res = 0; pntr = 1;
        G.clear(); dag.clear(); E.clear(); ver.clear(); bip.clear();
        G.resize(N); dag.resize(N); bip.resize(M);
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&v1,&v2);
            E.push_back(make_pair(v1,v2));
            G[v1].push_back(v2);
        }
        memset(V,0,sizeof(V));
        for(int i=1;i<=n;i++) if (!V[i]) dfs(i);
        memset(disc,0,sizeof(disc));
        for(int i=1;i<=n;i++){
            if (!disc[i]){
                tarjan(i);
            }
        }
        while (!st.empty()) st.pop();
        for(int i=1;i<=n;i++) if (root[i]==i) ver.push_back(i);
        for(int i=0;i<E.size();i++){
            int u = find(E[i].first);
            int v = find(E[i].second);
            if (u==v) continue;
            dag[u].push_back(v);
        }
        for(int i=0;i<ver.size();i++) {
            memset(V,0,sizeof(V));
            dfs4(ver[i],ver[i]);
        }
        memset(match,0,sizeof(match));
        for(int i=0;i<ver.size();i++){
            int u = ver[i];
            memset(V2,0,sizeof(V2));
            res+=aug(u);
        }
        res = ver.size() - res;
        printf("Case %d: %d\n",t1,res);
    }
}