#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#include <queue>

using namespace std;
using ll = long long;
using ld = long double;
mt19937 rd(3231213214);
const ll INF = 1e18, MOD = 1e9 + 7;
const int SZ = 2e3 + 1;

vector<pair<int, int>> g[SZ];
vector<pair<int, int>> rg[SZ];
int good_used[SZ];
int big_used = 0;

void find_good(int v, int mask) {
	static vector<int> d;
	d.push_back(v);
	good_used[v] = big_used;
	while (!d.empty()) {
		v = d.back();
		d.pop_back();
		for (auto e : g[v]) {
			if (good_used[e.first] == big_used || bool((mask >> e.second) & 1))
				continue;
			good_used[e.first] = big_used;
			d.push_back(e.first);
		}
		for (auto e : rg[v]) {
			if (good_used[e.first] == big_used || !bool((mask >> e.second) & 1))
				continue;
			good_used[e.first] = big_used;
			d.push_back(e.first);
		}
	}
}

void solve() {
	int n, m, G;
	cin >> n >> m >> G;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back({ v, i });
		rg[v].push_back({ u, i });
	}

	vector<vector<bool>> css(n + 1, vector<bool>(n + 1, 0));
	vector<vector<bool>> css2(n + 1, vector<bool>(n + 1, 0));
	for (int i = 1; i <= n; i++) {
		big_used++;
		find_good(i, 0);
		for (int j = 1; j <= n; j++)
			css[i][j] = (good_used[j] == big_used);
	}

	vector<int> cnt1(1 << m);
	cnt1[0] = 0;
	for (int i = 1; i < (1 << m); i++)
		cnt1[i] = 1 + cnt1[(i - 1) & i];

	vector<bool> good(1 << m, 0);
	int ans = 0, cnt = 1;
	for (int mask = 1; mask < (1 << m); mask++) {
		for (int i = 1; i <= n; i++) {
			big_used++;
			find_good(i, mask);
			for (int j = 1; j <= n; j++)
				css2[i][j] = (good_used[j] == big_used);
		}

		good[mask] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if ((css[i][j] && css[j][i]) != (css2[i][j] && css2[j][i])) {
					good[mask] = 0;
					break;
				}
			}
			if (!good[mask])
				break;
		}
		for (int i = 0; i < m; i++) {
			if ((mask >> i) & 1)
				good[mask] = good[mask] || good[mask ^ (1 << i)];
		}
		
		if (!good[mask] && cnt1[mask] >= ans) {
			if (cnt1[mask] > ans) {
				ans = cnt1[mask];
				cnt = 0;
			}
			cnt++;
		}
	}
	cout << ans << ' ' << cnt;
	return;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	solve();
}