#include<stdio.h>
#include<iostream>
using namespace std;
int k, n;
int A[30][30], B[30], ans;
void f(int c, int d){
	if(ans<d) ans = d;
	if(B[c]==k) return;
	B[c]+=1;
	for(int i=1;i<=n;i++) if(A[c][i]==1) f(i,d+1);
	B[c]-=1;
}
int main(){
	int m, i;
	char a, b;
	scanf("%d %d %d", &n, &m, &k);
	for(i=0;i<m;i++){
		cin >> a >> b;
		A[a-'A'+1][b-'A'+1]=A[b-'A'+1][a-'A'+1]=1;
	}
	for(i=2;i<=n;i++){
		if(A[1][i]==1){
			f(i,1);
		}
	}
	if(ans==0)	printf("0");
	else printf("%d", ans-1);
}