1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 #include <stack>
  8 using namespace std;
  9 
 10 const int MAXN = (1000 + 10);
 11 const int MAXM = (10000 + 10);
 12 int n, m;
 13 int cnt, scc_count;
 14 bool Instack[MAXN];
 15 int low[MAXN], dfn[MAXN], color[MAXN];
 16 vector<int > g[MAXN];
 17 stack<int > S;
 18 
 19 void Tarjan(int u)
 20 {
 21     low[u] = dfn[u] = ++cnt;
 22     Instack[u] = true;
 23     S.push(u);
 24     for (int i = 0; i < (int)g[u].size(); i++) {
 25         int v = g[u][i];
 26         if (dfn[v] == 0) {
 27             Tarjan(v);
 28             low[u] = min(low[u], low[v]);
 29         } else if (Instack[v]) {
 30             low[u] = min(low[u], dfn[v]);
 31         }
 32     }
 33     if (low[u] == dfn[u]) {
 34         scc_count++;
 35         int v;
 36         do {
 37             v = S.top();
 38             S.pop();
 39             Instack[v] = false;
 40             color[v] = scc_count;
 41         } while (u != v);
 42     }
 43 }
 44 
 45 bool Isok[MAXN][MAXN];
 46 bool mark[MAXN];
 47 vector<int > reg[MAXN];
 48 
 49 void bfs(int st)
 50 {
 51     memset(mark, false, sizeof(mark));
 52     queue<int >que;
 53     que.push(st);
 54     mark[st] = true;
 55     while (!que.empty()) {
 56         int u = que.front();
 57         que.pop();
 58         for (int i = 0; i < (int)reg[u].size(); i++) {
 59             int v = reg[u][i];
 60             if (!mark[v]) {
 61                 mark[v] = true;
 62                 que.push(v);
 63             }
 64         }
 65     }
 66 }
 67 
 68 void Build()
 69 {
 70     for (int i = 1; i <= scc_count; i++) {
 71         reg[i].clear();
 72     }
 73     for (int i = 1; i <= scc_count; i++) {
 74         for (int j = 1; j <= scc_count; j++) {
 75             if (i != j && Isok[i][j]) {
 76                 reg[i].push_back(j);
 77             }
 78         }
 79     }
 80 }
 81 
 82 int lx[MAXN], ly[MAXN];
 83 int distx[MAXN], disty[MAXN];
 84 
 85 bool MaxMatch_bfs()
 86 {
 87     bool flag = false;
 88     memset(distx, 0, sizeof(distx));
 89     memset(disty, 0, sizeof(disty));
 90     queue<int > que;
 91     for (int i = 1; i <= scc_count; i++) {
 92         if (lx[i] == -1) que.push(i);
 93     }
 94     while (!que.empty()) {
 95         int u = que.front();
 96         que.pop();
 97         for (int i = 0; i < (int)reg[u].size(); i++) {
 98             int v = reg[u][i];
 99             if (disty[v] == 0) {
100                 disty[v] = distx[u] + 1;
101                 if (ly[v] == -1) flag = true;
102                 else {
103                     distx[ly[v]] = disty[v] + 1;
104                     que.push(ly[v]);
105                 }
106             }
107         }
108     }
109     return flag;
110 }
111 
112 int dfs(int u)
113 {
114     for (int i = 0; i < (int)reg[u].size(); i++) {
115         int v = reg[u][i];
116         if (disty[v] == distx[u] + 1) {
117             disty[v] = 0;
118             if (ly[v] == -1 || dfs(ly[v])) {
119                 ly[v] = u;
120                 lx[u] = v;
121                 return 1;
122             }
123         }
124     }
125     return 0;
126 }
127 
128 int MaxMatch()
129 {
130     memset(lx, -1, sizeof(lx));
131     memset(ly, -1, sizeof(ly));
132     int res = 0;
133     while (MaxMatch_bfs()) {
134         for (int i = 1; i <= scc_count; i++) {
135             if (lx[i] == -1) res += dfs(i);
136         }
137     }
138     return res;
139 }
140 
141 
142 int main()
143 {
144     int _case, t = 1;
145     scanf("%d", &_case);
146     while (_case--) {
147         scanf("%d %d", &n, &m);
148         for (int i = 1; i <= n; i++) {
149             g[i].clear();
150             reg[i].clear();
151         }
152         while (m--) {
153             int u, v;
154             scanf("%d %d", &u, &v);
155             g[u].push_back(v);
156         }
157         //强联通缩点重建图
158         cnt = scc_count = 0;
159         memset(dfn, 0, sizeof(dfn));
160         for (int i = 1; i <= n; i++) {
161             if (dfn[i] == 0) Tarjan(i);
162         }
163         for (int u = 1; u <= n; u++) {
164             for (int i = 0; i < (int)g[u].size(); i++) {
165                 int v = g[u][i];
166                 if (color[u] != color[v]) {
167                     reg[color[u]].push_back(color[v]);
168                 }
169             }
170         }
171         //bfs求出新图中的任意两点之间是否可达
172         memset(Isok, false, sizeof(Isok));
173         for (int i = 1; i <= scc_count; i++) {
174             bfs(i);
175             for (int j = 1; j <= scc_count; j++) {
176                 if (mark[j]) {
177                     Isok[i][j] = true;
178                 }
179             }
180         }
181         //对于那些可达的点重新连边
182         Build();
183         //bfs求解最大匹配；
184         //最小路径覆盖 = 顶点数 - 最大匹配数
185         int ans = MaxMatch();
186         printf("Case %d: %d\n", t++, scc_count- ans);
187     }
188     return 0;
189 }