#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int head[N], cnt = -1, n, m, low[N], dfn[N], res, tot;

struct node {
	int to, nxt;
} e[N << 2];

void add(int x, int y) {
	e[++cnt].nxt = head[x];
	head[x] = cnt;
	e[cnt].to = y;
}

void tarjan(int x, int lst) {
	//cout << x << " " << lst << endl;
	low[x] = dfn[x] = ++tot;
	for (int i = head[x]; i != -1; i = e[i].nxt) {
		int v = e[i].to;
		if (i == (lst ^ 1))
			continue;
		if (!dfn[v]) {
			tarjan(v, i);
			low[x] = min(low[x], low[v]);
			if (low[v] > dfn[x])
				res++;
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

int main() {
	while(cin >> n >> m){
		memset(head, -1, sizeof(head));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		tot = 0;
		cnt = -1;
		res = 0;
		for (int i = 1; i <= m; i++) {
			int x, y;
			cin >> x >> y;
			add(x, y);
			add(y, x);
		}
		for (int i = 1; i <= n; i++) {
			if (!dfn[i])
				tarjan(i, -1);
		}
		cout << res << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int head[N], cnt = -1, n, m, low[N], dfn[N], res, tot;

struct node {
	int to, nxt;
} ;

struct edge {
	int v, id;
};
vector<edge>e[N];


void tarjan(int x, int lst) {
	low[x] = dfn[x] = ++tot;
	for (int i = 0; i < e[x].size(); i++) {
		if (e[x][i].id == lst)
			continue;
		int v = e[x][i].v;
		if (!dfn[v]) {
			tarjan(v, e[x][i].id);
			low[x] = min(low[x], low[v]);
			if (low[v] > dfn[x])
				res++;
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

int main() {
	while (cin >> n >> m) {
		tot = 0;res = 0;
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		for (int i = 1; i <= n; i++)
			e[i].clear();
		for (int i = 1; i <= m; i++) {
			int x, y;
			cin >> x >> y;
			e[x].push_back({y, i});
			e[y].push_back({x, i});
		}
		for (int i = 1; i <= n; i++) {
			if (!dfn[i])
				tarjan(i, -1);
		}
		cout << res << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
int n, m, dfn[N], low[N], cut[N], res;
int cnt;

struct node {
	int v, id;
};
vector<node>e[N];

void tarjan(int x, int lst, int rt) {
	dfn[x] = low[x] = ++cnt;
	int son = 0;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (id == lst)
			continue;
		if (!dfn[v]) {
			tarjan(v, e[x][i].id, rt);
			son++;
			low[x] = min(low[x], low[v]);
			if (x != rt && low[v] >= dfn[x])
				cut[x] = 1;
			if (x == rt && son > 1)
				cut[x] = 1;
		} else
			low[x] = min(low[x], dfn[v]);
	}

}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i, -1, i);
	}
	for (int i = 1; i <= n; i++) {
		if (cut[i])
			res++;
	}
	cout << res << endl;
	for (int i = 1; i <= n; i++) {
		if (cut[i])
			cout << i <<' ';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, low[N], dfn[N], id[N], cnt, tot;
vector<int>edcc[N];

struct node {
	int v, lst;
};
vector<node>e[N];
stack<int>stk;

void tarjan(int x, int lst) {
	low[x] = dfn[x] = ++cnt;
	stk.push(x);
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].lst;
		if (id == lst)
			continue;
		if (!dfn[v]) {
			tarjan(v, id);
			low[x] = min(low[x], low[v]);
		} else
			low[x] = min(low[x], dfn[v]);
	}
	if (low[x] == dfn[x]) {
		int v;
		++tot;
		do {
			v = stk.top();
			stk.pop();
			edcc[tot].push_back(v);
		} while (v != x);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i, -1);
	}
	cout << tot << endl;
	for (int i = 1; i <= tot; i++) {
		cout << edcc[i].size() << " ";
		for (auto v : edcc[i]) {
			cout << v << ' ';
		}
		cout << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, low[N], dfn[N], cnt, tot;
stack<int>stk;
vector<int>pdcc[N];

struct node {
	int v, lst;
};
vector<node>e[N];

void tarjan(int x, int lst, int rt) {
	dfn[x] = low[x] = ++cnt;
	if (e[x].size() == 0 && x == rt) {
		++tot;
		pdcc[tot].push_back(x);
		return;
	}
	stk.push(x);
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].lst;
		if (id == lst)
			continue;
		if (!dfn[v]) {
			tarjan(v, id, rt);
			low[x] = min(low[x], low[v]);
			if (low[v] >= dfn[x]) {
				int V;
				++tot;
				do {
					V = stk.top();
					stk.pop();
					pdcc[tot].push_back(V);
				} while (V != v);
				pdcc[tot].push_back(x);
			}
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		if(x==y)continue;
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i, -1, i);
	}
	cout << tot << endl;
	for (int i = 1; i <= tot; i++) {
		cout << pdcc[i].size() << " ";
		for (auto v : pdcc[i]) {
			cout << v << " ";
		}
		cout << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

struct node {
	int v, id;
};
vector<node>e[N];
int n, m, dfn[N], low[N], cnt, tot, vis[1000005], f[N], res, ans,book[N];

void tarjan(int x, int lst) {
	dfn[x] = low[x] = ++cnt;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (id == lst)
			continue;
		if (!dfn[v]) {
			tarjan(v, id);
			low[x] = min(low[x], low[v]);
			if (low[v] > dfn[x])
				vis[id] = 1, ans++;
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

void dfs(int x, int fa) {
	book[x] = 1;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (v == fa || book[v]==1)
			continue;
		dfs(v, x);
		res = max(res, f[x] + f[v] + vis[id]);
		f[x] = max(f[x], f[v] + vis[id]);
	}
}

int main() {
	while (cin >> n >> m) {
		for (int i = 1; i <= n; i++) {
			dfn[i] = low[i]  = f[i] = 0;
			e[i].clear();
		}
		memset(vis,0,sizeof(vis));
		cnt = tot = ans = res = 0;
		for (int i = 1; i <= m; i++) {
			int x, y;
			cin >> x >> y;
			e[x].push_back({y, i});
			e[y].push_back({x, i});
		}
		for (int i = 1; i <= n; i++) {
			if (!dfn[i]) {
				tarjan(i, -1);
			}
		}
		dfs(1, 0);
		cout << ans - res << endl;
	}

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, dfn[N], low[N], cnt, tot;
int dep[N], fa[N], vis[N], mp[N], res;

struct node {
	int v, id;
};
vector<node>e[N];

void tarjan(int x, int lst) {
	dfn[x] = low[x] = ++cnt;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (id == lst)
			continue;
		if (!dfn[v]) {
			tarjan(v, id);
			fa[v] = x;
			mp[v] = id;
			dep[v] = dep[x] + 1;
			low[x] = min(low[x], low[v]);
			if (low[v] > dfn[x]) {
				vis[id] = 1;
				res++;
			}
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i, -1);
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if (x == y){
			cout<<res<<endl;
			continue;
		}
		while (x != y) {
			if (dep[x] > dep[y])
				swap(x, y);
			if (vis[mp[y]] == 1) {
				vis[mp[y]] = 0;
				res--;
			}
			y = fa[y];
		}
		cout << res << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, m, dfn[N], low[N], cnt, tot, del, cut[N];
int U[N], V[N];

struct node {
	int v, id;
};
vector<node>e[N];

void tarjan(int x, int lst, int rt) {
	low[x] = dfn[x] = ++cnt;
	int son = 0;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (id == lst || v == del)
			continue;
		if (!dfn[v]) {
			son++;
			tarjan(v, id, rt);
			low[x] = min(low[x], low[v]);
			if (x == rt && son > 1)
				cut[x]++;
			if (x != rt && low[v] >= dfn[x])
				cut[x]++;
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

int main() {
	while (cin >> n >> m) {
		int res = 0;
		for (int i = 1; i <= n; i++)
			e[i].clear();
		for (int i = 1; i <= m; i++) {
			int x, y;
			cin >> U[i] >> V[i];
			U[i]++;
			V[i]++;
			e[U[i]].push_back({V[i], i});
			e[V[i]].push_back({U[i], i});
		}
		for (int i = 1; i <= n; i++) {
			del = i;
			for (int j = 1; j <= n; j++) {
				dfn[j] = low[j] = cut[j] = 0;
			}
			cnt = 0, tot = 0;
			for (int j = 1; j <= n; j++) {
				if (!dfn[j] && j != i) {
					tarjan(j, -1, j);
					tot++;
				}
			}
			for (int j = 1; j <= n; j++) {
				res = max(res, tot + cut[j]);
			}
		}
		cout << res << endl;
	}


	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2100005;
int n, m, dfn[N], low[N], cnt, tot, U[N], V[N];

struct node {
	int v, id;
};
vector<node>e[N];
set<int>ans;

stack<int>stk;
void tarjan(int x, int lst, int rt) {
	dfn[x] = low[x] = ++cnt;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (lst == id)
			continue;
		if (!dfn[v]) {
			stk.push(id);
			tarjan(v, id, rt);
			low[x] = min(low[x], low[v]);
			if (low[v] >= dfn[x]) {
				vector<int>edge;
				int t;
				do {
					t = stk.top();
					stk.pop();
					edge.push_back(t);
				} while (t != id);
				set<int>nodes;
				for (auto j : edge) {
					nodes.insert(U[j]);
					nodes.insert(V[j]);
				}
				if (nodes.size() == edge.size()) {
					for (auto j : edge) {
						ans.insert(j);
					}
				}
			}
		} else
			low[x] = min(low[x], dfn[v]), stk.push(id);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back({y, i});
		U[i] = x;
		V[i] = y;
		e[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i, -1, i);
	}
	cout << ans.size() << endl;
//	sort(ans.begin(), ans.end());
	for (auto v : ans) {
		cout << v << " ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, low[N], dfn[N], cnt, tot, cut[N];
vector<int>dcc[N];

struct node {
	int v, id;
};
stack<int>stk;
vector<node>e[N];

void tarjan(int x, int lst, int rt) {
	dfn[x] = low[x] = ++cnt;
	stk.push(x);
	int son = 0;
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int id = e[x][i].id;
		if (id == lst)
			continue;
		if (!dfn[v]) {
			son++;
			tarjan(v, id, rt);
			low[x] = min(low[x], low[v]);
			if (x == rt && son > 1)
				cut[x] = 1;
			if (x != rt && low[v] >= dfn[x])
				cut[x] = 1;
			if (low[v] >= dfn[x]) {
				tot++;
				int V;
				do {
					V = stk.top();
					stk.pop();
					dcc[tot].push_back(V);
				} while (V != v);
				dcc[tot].push_back(x);
			}
		} else
			low[x] = min(low[x], dfn[v]);
	}
}

int main() {
	int Case = 0;
	while (cin >> n) {
		int Max = 0;
		if (!n)
			break;
		for (int i = 1; i <= 500; i++) {
			e[i].clear();
			dcc[i].clear();
			low[i] = dfn[i] = cut[i] = 0;
		}
		cnt = 0;
		tot = 0;
		for (int i = 1; i <= n; i++) {
			int x, y;
			cin >> x >> y;
			e[x].push_back({y, i});
			e[y].push_back({x, i});
			Max = max(Max, max(x, y));
		}
		for (int i = 1; i <= Max; i++) {
			if (!dfn[i])
				tarjan(i, -1, i);
		}
		int res1 = 0, res2 = 1;
		for (int i = 1; i <= tot; i++) {
			int C = 0;
			for (auto v : dcc[i]) {
				C += cut[v];
			}
			if (C == 0)
				res1 += 2, res2 *= (dcc[i].size() * (dcc[i].size() - 1)) / 2;
			if (C == 1)
				res1++, res2 *= dcc[i].size() - 1;
		}
		cout << "Case " << ++Case << ": " << res1 << " " << res2 << endl;
	}
	return 0;
}