# tioj 1253 砲打皮皮

https://tioj.ck.tp.edu.tw/problems/1253
* 一個強者物質能消滅整列或整行，也就是一個x或y
* 所以把皮皮的x, y座標互相連成二分圖，而目標就是把每條線都涵蓋到（也就是最小點覆蓋）
* 假設有(a, b), (a, c), (a, d)這些皮皮，這樣圖就是左邊的x=a連三條分別到y=b,c,d。所以如果選x=a，擇三條線都會覆蓋到（aka三個皮皮都消滅），成為最小點覆蓋。但如果選y=b，只有一條a - b的線被覆蓋到。
* 已知二分圖最大匹配=二分圖最小點覆蓋

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

struct bpt{
    vector<int> lg[1010];
    int lm[1010], rm[1010], done[1010];

    bool dfs(int v){
        done[v]=1;
        for(auto a:lg[v]){
            if(rm[a]==-1 || (!done[rm[a]] && dfs(rm[a]))){
                lm[v]=a;
                rm[a]=v;
                return 1;
            }
        }
        return 0;
    }

    LL matching(int n){
        LL ans=0;
        memset(lm, -1, sizeof(lm));
        memset(rm, -1, sizeof(rm));
        rep(i,1,n+1){
            if(lg[i].empty()) continue;
            memset(done, 0, sizeof(done));
            if(dfs(i)) ans++;
        }
        return ans;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL n, k, cnt=0;
    while(cin>>n>>k){
        if(n==0) break;
        bpt pp;
        int a, b;
        rep(i,0,k){
            cin>>a>>b;
            pp.lg[a].push_back(b);
        }
        cout<<"Case #"<<++cnt<<":"<<pp.matching(n)<<NL;
    }
}