#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
//#include <cmath>
//#include <numeric>

//#pragma GCC optimize("O3, unroll-loops")
//#pragma GCC target("avx2, avx, lzcnt, popcnt, bmi, bmi2")

using namespace std;
#define int long long

void dfs1(int v, vector<vector<int>>& gr, vector<int>& order, vector<int>& used) {
	used[v] = 1;
	for (int u : gr[v]) {
		if (used[u] == 0) {
			dfs1(u, gr, order, used);
		}
	}
	order.push_back(v);
}

void dfs2(int v, int cnt, vector<vector<int>>& gr, vector<int>& comp) {
	comp[v] = cnt;
	for (int u : gr[v]) {
		if (comp[u] == -1) {
			dfs2(u, cnt, gr, comp);
		}
	}
}

int n, m;

vector<int> solve(vector<vector<int>>& gr, vector<vector<int>>& obr) {
	vector<int> order, used(n);
	for (int i = 0; i < n; i++) {
		if (used[i] == 0) {
			dfs1(i, gr, order, used);
		}
	}
	reverse(order.begin(), order.end());
	int cnt = 0;
	vector<int> comp(n, -1);
	for (int i = 0; i < n; i++) {
		if (comp[order[i]] == -1) {
			dfs2(order[i], cnt, obr, comp);
			cnt++;
		}
	}
	return comp;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int g;
	cin >> n >> m >> g;
	vector<vector<int>> edges(m);
	vector<int> A(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edges[i] = { a, b };
	}
	vector<bool> flag(1 << m, false);
	vector<int> st;
	for (int mask = 0; mask < (1 << m); mask++) {
		vector<vector<int>> gr(n), obr(n);
		for (int i = 0; i < m; i++) {
			if (mask & (1 << i)) {
				gr[edges[i][1]].push_back(edges[i][0]);
				obr[edges[i][0]].push_back(edges[i][1]);
			}
			else {
				obr[edges[i][1]].push_back(edges[i][0]);
				gr[edges[i][0]].push_back(edges[i][1]);
			}
		}
		vector<int> temp = solve(gr, obr);
		if (mask == 0) {
			st = temp;
			flag[mask] = true;
		}
		else {
			vector<int> enc(n, -1);
			vector<bool> cod(n, false);
			bool prov = true;
			for (int i = 0; i < n; i++) {
				if (enc[st[i]] == -1) {
					if (cod[temp[i]]) {
						prov = false;
						break;
					}
					enc[st[i]] = temp[i];
					cod[temp[i]] = true;
				}
				else if (enc[st[i]] != temp[i]) {
					prov = false;
					break;
				}
			}
			if (prov) {
				flag[mask] = true;
			}
		}
	}
	vector<bool> nflag(1 << m);
	nflag[0] = false;
	int maxi = 0, res = 1;
	for (int mask = 1; mask < (1 << m); mask++) {
		int ind1 = -1, ind2 = -1, cnt = 0;
		for (int i = 0; i < m; i++) {
			if (mask & (1 << i)) {
				if (ind1 == -1) {
					ind1 = i;
				}
				else {
					ind2 = i;
				}
				cnt++;
			}
		}
		if (cnt == 1) {
			nflag[mask] = flag[mask];
		}
		else {
			flag[mask] = flag[mask] or flag[mask - (1 << ind1)] or flag[mask - (1 << ind2)];
		}
		if (not nflag[mask]) {
			if (cnt > maxi) {
				maxi = cnt;
				res = 1;
			}
			else if (cnt == maxi) {
				res++;
			}
		}
	}
	cout << maxi << '\n' << res;
}