#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

string x, x2;
int q, w, e, r, arr[30];

vector<int> v[30];

void f(int a, int s) {
	r = max(r, s);
	if (arr[a] == e) {
		return;
	}
	++arr[a];
	for (auto& i : v[a]) {
		f(i, s + 1);
	}
	--arr[a];
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> q >> w >> e;
	while (w--) {
		cin >> x >> x2;
		v[x[0] - 'A'].push_back(x2[0] - 'A');
		v[x2[0] - 'A'].push_back(x[0] - 'A');
	}
	f(0, 0);
	cout << max(0, r - 1) << '\n';
	return 0;
}