#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <unordered_set>
#include <algorithm>

using namespace std;

using ll = long long;

#pragma GCC optimaze("Ofast");

int n, m, t;

void dfs(int v, vector<vector<int>>& gr, vector<int>& us, vector<int>& top) {
	us[v] = 1;
	for (int u : gr[v]) {
		if (us[u]) continue;
		dfs(u, gr, us, top);
	}
	top.push_back(v);
}

void dfs2(int v, int &T, vector<vector<int>>& gr, vector<int>& us) {
	us[v] = T;
	T = min(T, v+1);
	for (int u : gr[v]) {
		if (us[u]) continue;
		dfs2(u, T, gr, us);
	}
	us[v] = T;
}

vector<int> css(int x, vector<pair<int, int>>& e) {
	vector<vector<int>> gr(n), gr2(n);
	for (int i = 0; i < m; i++) {
		if (x & (1 << i)) gr[e[i].second].push_back(e[i].first);
		else gr[e[i].first].push_back(e[i].second);
	}
	vector<int> us(n);
	vector<int> top;
	for (int i = 0; i < n; i++) {
		if (us[i]) continue;
		dfs(i, gr, us, top);
	}
	for (int i = 0; i < n; i++) {
		us[i] = 0;
		for (int u : gr[i]) {
			gr2[u].push_back(i);
		}
	}
	int X;
	for (int i = n - 1; i > -1; i--) {
		if (us[top[i]]) continue;
		X = top[i] + 1;
		dfs2(top[i], X, gr2, us);
	}
	return us;
}

vector<unordered_set<int>> pr;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m >> t;
	vector<pair<int, int>> e;
	pr.resize(n);
	vector<int> us(n);
	for (int i = 0; i < m; i++) {
		int A, B;
		cin >> A >> B;
		A--;
		B--;
		e.push_back({ A, B });
	}
	vector<int> ok = css(0, e);
	vector<bool> dp(1 << m);
	for (int i = 1; i < (1 << m); i++) {
		for (int j = 0; j < m; j++) if (i & (1 << j) && dp[i ^ (1 << j)]) dp[i] = 1;
		if (dp[i]) continue;
		vector<int> v = css(i, e);
		if (v == ok) dp[i] = 1;
		
		
	}
	ll ma = 0, cnt = 0;
	for (int i = 0; i < (1 << m); i++) {
		if (dp[i]) continue;
		int cn = 0;
		for (int j = 0; j < m; j++) if (i & (1 << j)) cn++;
		if (cn == ma) cnt++;
		else if(cn>ma){
			ma = cn;
			cnt = 1;
		}
	}
	cout << ma << "\n" << cnt;
}



