# include <bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
int que[410],dis[410],f[2010],w1[410],w2[410][410];
vector<int> G[410],H[410];
bitset<401> st[410];
struct Edge
{
	int u,v;
	Edge(){}
	Edge(int u,int v):u(u),v(v){}
	bool operator<(const Edge &t)const{return dis[u]>dis[t.u];}
}E[2010];
inline void chkmax(int &x,const int &y){x=max(x,y);}
int main()
{
	int T,n,m,u,v;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		int l=0,r=0,ans=0,tot=0;
		scanf("%d%d",&n,&m);
		for(int i=0;i<m;i++)
		{
			scanf("%d,%d",&u,&v);u++;v++;
			G[u].push_back(v);
			G[v].push_back(u);
			st[u].set(v);st[v].set(u);
		}
		for(int i=1;i<=n;i++) w1[i]=st[i].count();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				w2[i][j]=(st[i]&st[j]).count();
		fill(dis+1,dis+n+1,INF);
		dis[que[r++]=2]=0;
		while(l<r)
		{
			int u=que[l++];
			for(int v:G[u])
				if(dis[u]+1<dis[v])
					dis[que[r++]=v]=dis[u]+1;
		}
		for(int u=1;u<=n;u++)
			for(int v:G[u])
				if(dis[v]+1==dis[u])
					E[++tot]=Edge(u,v);
		sort(E+1,E+tot+1);
		for(int i=1;i<=tot;i++) H[E[i].u].push_back(i);
		fill(f+1,f+tot+1,-INF);
		for(int i:H[1])
		{
			int u=E[i].u,v=E[i].v;
			f[i]=w1[v]-w2[u][v];
		}
		for(int i=1;i<=tot;i++)
		{
			if(f[i]<=-INF) continue;
			int u=E[i].u,v=E[i].v;
			bool flag=0;
			for(int j:H[v])
			{
				int w=E[j].v;
				flag|=(w==2);
				chkmax(f[j],f[i]+w1[w]-w2[u][w]-w2[v][w]+(st[u]&st[v]&st[w]).count());
			}
			if(flag) chkmax(ans,f[i]);
		}
		ans+=st[1].count();
		printf("Case #%d: %d %d\n",_,dis[1]-1,ans-(dis[1]>1?dis[1]:0));
		for(int i=1;i<=n;i++) G[i].clear(),H[i].clear(),st[i].reset();
	}
	return 0;
}