miningbusiness.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define INF 10000000
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

vector<int> adj[100005];
int lowlink[50005];
int dfsID[50005];
int vis[50005] = {};
bool isCut[50005] = {};

vector<vector<pii>> twovcc;
stack<pii> stac;

int id = 1;
void dfs(int u, int parent) {
	lowlink[u] = id;
	dfsID[u] = id++;

	vis[u] = 1;

	// cout << u << endl;
	for(int v : adj[u]) {
		if(v == parent) continue;
		if(vis[v] == 0) {
			stac.push(mp(u, v));
			dfs(v, u);
			lowlink[u] = min(lowlink[u], lowlink[v]);
			if(dfsID[u] <= lowlink[v] && parent != -1) {
				isCut[u] = true;
				// cout << u << " is cut " << endl;
				vector<pii> edges;
				while(true) {
					pii top = stac.top();
					stac.pop();
					edges.pb(top);
					if(top.f == u) break;
				}
				twovcc.pb(edges);
			}
		} else if(vis[v] == 1) {
			lowlink[u] = min(lowlink[u], dfsID[v]);
			stac.push(mp(u, v));
		}
	}
	vis[u] = 2;

	if(parent == -1) { // you are root node
		int cnt = 0;
		while(!stac.empty()) {
			vector<pii> edges;
			while(true) {
				pii top = stac.top();
				stac.pop();
				edges.pb(top);
				if(top.f == u) break;
			}
			twovcc.pb(edges);
			cnt++;
		}
		isCut[u] = cnt > 1;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	
	int e;
	int cases = 0;
	for(cin >> e;e != 0;cin >> e) {
		twovcc.clear();
		for(int i = 0;i < 50005;i ++) {
			vis[i] = false;
			dfsID[i] = lowlink[i] = -1;
			adj[i].clear();
			isCut[i] = false;
		}

		int a, b;
		int n = 0;
		for(int i = 0;i < e;i ++) {
			cin >> a >> b;
			n = max(n, max(a, b));
			a--;b--;
			adj[a].pb(b);
			adj[b].pb(a);
		}
		dfs(0, -1);
		
		cout << "Case " << (++cases) << ": ";
		if(twovcc.size() == 1) {
			cout << 2 << " " << (((ll)n * (n - 1)) / 2) << endl;
			return 0;
		}

		ll tot = 1;
		ll totvcc = 0;

		for(vector<pii> v : twovcc) {
			set<int> verts;
			for(pii p : v) {
				// cout << p.f << "," << p.s << " ";
				verts.insert(p.f);
				verts.insert(p.s);
			}
			// cout << endl;
			int numCut = 0;
			for(set<int>::iterator it = verts.begin(); it != verts.end();it++) {
				if(isCut[*it]) numCut++;
			}
			if(numCut == 1) {
				totvcc++;
				tot *= verts.size() - 1;
			}
		}
		cout << totvcc << " " << tot << endl;

	}
}