#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <math.h>
#include <string>
#include <vector>
#include <chrono>
#include <random>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <set>
#define endl '\n'
#define mp make_pair

using namespace std;
using i64 = long long;
using ld = long double;

const i64 INF = 1e18 + 5;

mt19937 rnd(29);

i64 gcd_ext(i64 a, i64 b, i64& x, i64& y) {
	if (b == 0) {
		x = 1; y = 0;
		return a;
	}
	i64 x1 = 0, y1 = 0;
	i64 c = gcd_ext(b, a % b, x1, y1);
	x = y1, y = (-y1 * (a / b) + x1);
	return c;
}

i64 gcd(i64 a, i64 b) {
	while (b) swap(b, a %= b);
	return a;
}

const i64 S = 21, md = 1e9 + 7, B = 197;
vector <pair<i64, i64>> edge;

struct getHashGr {
	vector <i64> p[S], gr[S], color[S];
	vector <i64> topsort;
	i64 used[S];
	i64 n;
	void init(i64 m) {
		n = m;
		fill(used, used + n + 1, 0);
		for (i64 x = 1; x <= n; ++x) {
			for (auto y : p[x]) {
				gr[y].push_back(x);
			}
		}
	}
	void clear() {
		for (i64 x = 1; x <= n; ++x) {
			p[x].clear();
			gr[x].clear();
			used[x] = 0;
			color[x].clear();
		}
		topsort.clear();
		return;
	}
	void dfs(i64 v) {
		used[v] = 1;
		for (auto x : p[v]) {
			if (!used[x]) {
				dfs(x);
			}
		}
		topsort.push_back(v);
		return;
	}
	void backDfs(i64 v, i64 clr) {
		used[v] = clr;
		color[clr].push_back(v);
		for (auto x : gr[v]) {
			if (!used[x]) {
				backDfs(x, clr);
			}
		}
		return;
	}
	i64 makeHash() {
		for (i64 x = 1; x <= n; ++x) {
			if (!used[x]) {
				dfs(x);
			}
		}
		fill(used + 1, used + n + 1, 0);
		reverse(topsort.begin(), topsort.end());
		i64 cnt = 0;
		for (auto x : topsort) {
			if (!used[x]) {
				++cnt;
				backDfs(x, cnt);
			}
		}
		i64 mult = 1;
		for (i64 x = 1; x <= cnt; ++x) {
			sort(color[x].begin(), color[x].end());
			i64 hsh = 0;
			for (auto y : color[x]) {
				hsh = (hsh * B + y) % md;
			}
			mult *= hsh;
			mult %= md;
		}
		return mult;
	}
};

vector <i64> rn;

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

	i64 n, m, q; cin >> n >> m >> q;

	getHashGr gr;

	for (i64 x = 1; x <= m; ++x) {
		i64 u, v; cin >> u >> v;
		gr.p[u].push_back(v);
		edge.push_back(mp(u, v));
	}

	gr.init(n);
	i64 comp = gr.makeHash();

	i64 ans = 0, sum = 1;

	for (i64 x = 1; x < (i64(1) << m); ++x) {
		i64 val = x;
		i64 summa = 0;
		for (i64 y = 0; y < m; ++y) {
			if ((val & 1) == 1) ++summa;
			val = (val >> 1);
		}
		i64 cnt = 0;
		for (i64 times = 0; times < (i64(1) << summa); ++times) {
			val = x;
			gr.clear();
			rn.clear();
			for (i64 y = 0; y < m; ++y) {
				if ((val & 1) == 0) gr.p[edge[y].first].push_back(edge[y].second);
				else rn.push_back(y);
				val = (val >> 1);
			}
			i64 val1 = times;
			for (i64 y = 0; y < rn.size(); ++y) {
				if ((val1 & 1) == 1) {
					gr.p[edge[rn[y]].first].push_back(edge[rn[y]].second);
				}
				else {
					gr.p[edge[rn[y]].second].push_back(edge[rn[y]].first);
				}
				val1 = (val1 >> 1);
			}
			gr.init(n);
			i64 comp11 = gr.makeHash();
			if (comp11 == comp) {
				++cnt;
			}
		}
		if (cnt == 1) {
			if (summa > ans) {
				ans = summa, sum = 1;
			}
			else if (summa == ans) {
				++sum;
			}
		}
	}

	cout << ans << endl << sum;
}