Ubiquitous Religions

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-06-19 15-56-44
  4**/
  5
  6#include <cstdio>
  7#include <cstring>
  8#include <iomanip>
  9#include <ctime>
 10#include <algorithm>
 11#include <iostream>
 12#include <string>
 13#include <vector>
 14#include <stack>
 15#include <bitset>
 16#include <complex>
 17#include <cstdlib>
 18#include <cmath>
 19#include <set>
 20#include <list>
 21#include <deque>
 22#include <map>
 23#include <queue>
 24
 25using namespace std;
 26
 27#ifdef DEBUG
 28string to_string(string s) {
 29	return '"' + s + '"';
 30}
 31
 32string to_string(const char* s) {
 33	return to_string((string) s);
 34}
 35
 36string to_string(bool b) {
 37return (b ? "true" : "false");
 38}
 39
 40template <typename A, typename B>
 41string to_string(pair<A, B> p) {
 42	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
 43}
 44
 45template <typename A>
 46string to_string(A v) {
 47	bool first = true;
 48	string res = "{";
 49	for (const auto &x : v) {
 50		if (!first) {
 51			res += ", ";
 52		}
 53		first = false;
 54		res += to_string(x);
 55	}
 56	res += "}";
 57	return res;
 58}
 59
 60void debug_out() { cerr << endl; }
 61
 62template <typename Head, typename... Tail>
 63void debug_out(Head H, Tail... T) {
 64	cerr << " " << to_string(H);
 65	debug_out(T...);
 66}
 67#endif
 68
 69#ifdef DEBUG
 70#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
 71#else
 72#define debug(...) 17
 73#endif
 74
 75#ifdef DEBUG
 76#define FAST_IO 17
 77#define cout cout << "-->"
 78#else
 79#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 80#define endl '\n'
 81#endif
 82
 83#define LL long long
 84#define ULL unsigned long long
 85#define rep(i, n) for(int i = 0; i < (n); ++i)
 86#define reep(i, n) for(int i = 0; i <= (n); ++i)
 87#define lop(i, a, n) for(int i = a; i < (n); ++i)
 88#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 89#define ALL(v) (v).begin(), (v).end()
 90#define PB push_back
 91#define VI vector<int>
 92#define PII pair<int,int>
 93#define FI first
 94#define SE second
 95#define SZ(x) ((int)(x).size())
 96
 97const double EPS = 1e-6;
 98const double PI = acos(-1.0);
 99const int INF = 0x3f3f3f3f;
100const LL LINF = 0x7f7f7f7f7f7f7f7f;
101const int MAXN = (int)1e6 + 10;
102const int MOD = (int)1e9 + 7;
103
104class UnionFind{
105	private:
106		int * parents;
107		int * sz;
108		int count;
109	public:
110		UnionFind(int n){
111			this->count = n;
112			parents = new int[n];
113			sz = new int[n];
114			for(int i = 0; i < n; ++i){
115				parents[i] = i;
116				sz[i] = 1;
117			}
118		}
119		~UnionFind(){
120			delete [] parents;
121			delete [] sz;
122		}
123
124		int find(int p){
125			while(p != parents[p]) p = parents[p];	
126			return p;
127		}
128
129		void unionElements(int p, int q){
130			int pRoot = find(p);
131			int qRoot = find(q);
132			
133			if(pRoot == qRoot) return;
134
135			if(sz[pRoot] < sz[qRoot]){
136				parents[pRoot] = qRoot;
137				sz[qRoot] += sz[pRoot];
138			}else{
139				parents[qRoot] = pRoot;
140				sz[pRoot] += sz[qRoot];
141			}
142		}
143
144		int ans(){
145			int cnt = 0;
146			for(int i = 0; i < this->count; ++i){
147				if(parents[i] == i) ++cnt;
148			}
149			return cnt;
150		}
151};
152
153int n, m, i, j, cnt = 0;
154
155int main(){
156	FAST_IO;
157
158	while(cin >> n >> m && (n || m)){
159		++cnt;
160		//if(n==0 && m==0) break;
161		UnionFind uf = UnionFind(n);
162		while(m--){
163			cin >> i >> j;
164			uf.unionElements(i-1, j-1);
165		}
166		cout << "Case " << cnt << ": " << uf.ans() << endl;
167	}
168
169	return 0;
170}