#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=4e4+5,M=8e6+5;
struct edge{int to,nex,w;}e[M<<1];
int TT,n,m,k,S,T,tot,head[N],_head[N],d[N];
basic_string<int>g[N];
inline void add(int u,int v,int w)
{
	e[++tot]={v,head[u],w};head[u]=tot;
	e[++tot]={u,head[v],0};head[v]=tot;
}
inline bool bfs()
{
	memset(d,0,sizeof(d));d[S]=1;queue<int>q;q.push(S);
	while(!q.empty())
	{
		int t=q.front();q.pop();
		for(int i=head[t];i;i=e[i].nex)
		{
			int to=e[i].to;
			if(!d[to]&&e[i].w>0) d[to]=d[t]+1,q.push(to);
		}
	}
	return d[T];
}
int dfs(int x,int F)
{
	if(x==T) return F;int tt=F;
	for(int &i=_head[x];i;i=e[i].nex)
	{
		int to=e[i].to;
		if(d[to]==d[x]+1&&e[i].w>0)
		{
			int t=dfs(to,min(tt,e[i].w));
			tt-=t;e[i].w-=t;e[i^1].w+=t;
			if(!tt) break;
		}
	}
	if(tt==F) d[x]=0;return F-tt;
}
inline int dinic()
{
	int s=0;
	while(bfs())
	{
		memcpy(_head,head,sizeof(head)),s+=dfs(S,2e9);
		if(s>k) return s;
	}
	return s;
}
inline bool chk(int x)
{
	tot=1;memset(head,0,sizeof(head));
	S=2;T=(x+1)*2*n-1;
	for(int i=1;i<=x;i++)
	{
		for(int j=n-1;j>1;j--)
			add((i-1)*2*n+j*2-1,(i-1)*2*n+j*2,1),add((i-1)*2*n+j*2-1,i*2*n+j*2,1e9);
		for(int j=1;j<=n;j++) for(int k:g[j])  
			add((i-1)*2*n+j*2,i*2*n+(k*2)-1,1e9);  
		add((i-1)*2*n+n*2-1,i*2*n+(n*2)-1,1e9); 
	}
	return dinic()<=k;
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>TT;
	for(int c=1;c<=TT;c++)
	{
		cin>>n>>m>>k;k--;
		for(int i=1,u,v;i<=m;i++) cin>>u>>v,u++,v++,g[u]+=v,g[v]+=u;
		int l=1,r=n+k,mid,ans=0;
		while(l<=r) mid=(l+r)>>1,chk(mid)?ans=mid,l=mid+1:r=mid-1;
		cout<<"Case #"<<c<<": "<<ans+2<<"\n";
		for(int i=1;i<=n;i++) g[i].clear();
	}
	
	return 0;
}