10583_UbiquitousReligions

#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, ans, pSet[50004];
bool p[50004];

void initSet(int n) {
    for (int i=0; i<=n; ++i) pSet[i] = i;
    memset(p, false, sizeof(p));
    ans = 0;
}

int findSet(int u){
    return(pSet[u] == u ? u : pSet[u] = findSet(pSet[u]));
}

void unionSet(int u, int v) {
    pSet[findSet(u)] = findSet(v);
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("uva10583.inp", "r", stdin);
    #endif // ONLINE_JUDGE

    int c = 0;
    while (1) {
        scanf("%d%d", &n, &m);
        if (n == 0) break;
        ++c; initSet(n);

        for (int i=0; i<m; ++i) {
            scanf("%d%d", &u, &v);
            unionSet(u, v);
        }

        for (int i=1; i<=n; ++i)
            if (!p[findSet(i)]) {
                ++ans; p[findSet(i)] = true;
            }

        printf("Case %d: %d\n", c, ans);
    }
}