#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#define all(v) v.begin(), v.end()
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<long long, long long> pii;

const ll SZ = 2000;

vector<ll> g[SZ];
vector<ll> g2[SZ];
ll used[SZ];
ll c[SZ];
ll c2[SZ];
vector<ll> path;

void dfs(ll v) {
	used[v] = 1;
	for (auto u : g[v]) {
		if (!used[u]) dfs(u);
	}
	path.push_back(v);
}

void dfs2(ll v, ll co) {
	c[v] = co;
	for (auto u : g2[v]) {
		if (!c[u]) dfs2(u, co);
	}
}

void solve() {
	ll n, m, h, v, u;
	cin >> n >> m >> h;
	vector<pii> edges;
	for (ll i = 0; i < m; i++) {
		cin >> v >> u;
		g[--v].push_back(--u);
		g2[u].push_back(v);
		edges.push_back({ v, u });
	}
	for (ll i = 0; i < n; i++) {
		if (!used[i]) dfs(i);
	}
	reverse(all(path));
	for (auto i : path) {
		if (!c[i]) {
			dfs2(i, i + 1);
		}
	}
	for (ll i = 0; i < n; i++) c2[i] = c[i];
	ll mid, l = 0, r = m + 1;
	vector<ll> ans(m + 1);
	ll cur = -1;
	for (ll mask = 0; mask < (1 << m); mask++) {
		ll cnt = 0;
		ll s = 0;
		for (ll i = 0; i < m; i++) {
			if ((mask >> i) & 1) s++;
		}
		if (s < cur) continue;
		for (ll mask2 = mask; mask2 >= 0; mask2 = (mask & (mask2 - 1))) {
			for (ll i = 0; i < n; i++) {
				g[i] = {};
				g2[i] = {};
				used[i] = 0;
				c[i] = 0;
				path = {};
			}
			for (ll i = 0; i < m; i++) {
				if (!((mask >> i) & 1)) {
					g[edges[i].fi].push_back(edges[i].se);
					g2[edges[i].se].push_back(edges[i].fi);
				}
				else {
					if ((mask2 >> i) & 1) {
						g[edges[i].fi].push_back(edges[i].se);
						g2[edges[i].se].push_back(edges[i].fi);
					}
					else {
						g2[edges[i].fi].push_back(edges[i].se);
						g[edges[i].se].push_back(edges[i].fi);
					}
				}
			}
			for (ll i = 0; i < n; i++) {
				if (!used[i]) dfs(i);
			}
			reverse(all(path));
			for (auto i : path) {
				if (!c[i]) {
					dfs2(i, i + 1);
				}
			}
			bool f = true;
			for (ll i = 0; i < n; i++) {
				if (c[i] != c2[i]) {
					f = false;
					break;
				}
			}
			//cout << mask << ' ' << mask2 << '\n';
			//for (ll i = 0; i < n; i++) cout << c[i] << ' ' << c2[i] << '\n';
			if (f) cnt++;
			if (cnt == 2) break;
			if (!mask2) break;
		}
		//cout << cnt << '\n';
		if (cnt == 2 || !cnt) continue;
		cur = max(cur, s);
		ans[s]++;
	}
	ll res = 0, resc = 1;
	for (ll i = 0; i <= m; i++) {
		if (ans[i]) {
			res = i;
			resc = ans[i];
		}
	}
	cout << res << '\n' << resc << '\n';
}

int main() {
	ll t = 1;
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	cin >> t;
#else
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#endif
	while (t--) solve();
}
