#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <array>
#include <queue>

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) a.begin(), a.end()
const ll N = 2001, MOD = 1e9 + 7;
ll n, m, group;
vector<ll> us, st, res; ll usnow;
void topsort(ll v, vector<vector<ll>>& g) {
	us[v] = usnow;
	for (ll u : g[v]) {
		if (us[u] < usnow) {
			topsort(u, g);
		}
	}
	st.push_back(v);
}
ll getmn(ll v, vector<vector<ll>>& g) {
	ll mn = v;
	us[v] = usnow;
	for (ll u : g[v]) {
		if (us[u] < usnow) {
			mn = min(mn, getmn(u, g));
		}
	}
	return mn;
}

void setmn(ll v, ll mn, vector<vector<ll>>& g) {
	res[v] = mn;
	us[v] = usnow;
	for (ll u : g[v]) {
		if (us[u] < usnow) {
			setmn(u, mn, g);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> group;
	vector<array<ll, 2>> e(m);
	for (ll i = 0; i < m; i++) {
		ll u, v;
		cin >> u >> v;
		e[i] = { u - 1, v - 1 };
	}
	us.resize(n, 0);
	usnow = 1;
	vector<char> is(1ll << m);
	vector<ll> res0;
	res.resize(n);
	for (ll mask = 0; mask < (1ll << m); mask++) {
		vector<vector<ll>> g(n), rg(n);
		for (ll i = 0; i < m; i++) {
			if ((mask >> i) & 1) {
				g[e[i][1]].push_back(e[i][0]);
				rg[e[i][0]].push_back(e[i][1]);
			}
			else {
				g[e[i][0]].push_back(e[i][1]);
				rg[e[i][1]].push_back(e[i][0]);
			}
		}
		st.clear();
		for (ll i = 0; i < n; i++) {
			if (us[i] < usnow) topsort(i, rg);
		}
		reverse(all(st));
		usnow++;
		for (ll x : st) {
			if (us[x] < usnow) {
				ll mn = getmn(x, g);
				usnow++;
				setmn(x, mn, g);
				usnow--;
			}
		}
		usnow += 2;
		is[mask] = (res == res0);
		if (mask == 0) res0 = res;
	}
	for (ll i = 0; i < m; i++) {
		for (ll mask = 0; mask < (1ll << m); mask++) {
			if (((mask >> i) & 1) == 0) {
				is[mask | (1 << i)] |= is[mask];
			}
		}
	}
	ll res = 0, cnt = 0;
	for (ll mask = 0; mask < (1ll << m); mask++) {
		if (!is[mask]) {
			ll nn = 0;
			for (ll i = 0; i < m; i++) nn += ((mask >> i) & 1);
			if (nn == res) cnt++;
			else if (nn > res) {
				res = nn;
				cnt = 1;
			}
		}
	}
	cout << res << "\n" << cnt << "\n";
	return 0;
}