#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long
const int MOD = 1e9 + 7;

bool get_bit(int x, int d) {
	return x >> d & 1;
}

struct DSU {
	vector <int> p;
	vector <int> sz;
	int n;

	DSU(int n) {
		this->n = n;
		p.resize(n);
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
		sz.resize(n, 1);
	}

	int get(int x) {
		if (p[x] == x) return x;
		return p[x] = get(p[x]);
	}

	bool merge(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) return 0;
		if (sz[x] > sz[y]) {
			swap(x, y);
		}
		p[x] = y;
		sz[y] += sz[x];
		return 1;
	}

	DSU() {}
};

DSU dsu;

int n, m, G;
vector <vector <int>> g;
vector <vector <int>> cg;
vector <pair <int, int>> eds;

int T;
vector <int> used;

bool dfs(int v, int target, int a, int b) {
	if (v == target) return 1;
	if (used[v] == T) return 0;
	used[v] = T;
	for (auto u : g[v]) {
		if (v == a && u == b) continue;
		if (dfs(u, target, a, b)) return 1;
	}
	return 0;
}

bool check(int v, int u) {
	T++;
	return dfs(v, u, v, u);
}

signed main() {
	cin >> n >> m >> G;
	g.resize(n);
	cg.resize(n);
	used.resize(n);
	T = 1;
	vector <vector <bool>> can(n, vector <bool>(n));
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		eds.push_back({ a, b });
	}
	for (auto [a, b] : eds) {
		can[a][b] = check(a, b);
		can[b][a] = check(b, a);
	}

	dsu = DSU(n);
	for (auto [a, b] : eds) {
		if (can[b][a]) {
			dsu.merge(a, b);
		}
	}
	vector <int> cnt_poss(1 << m);
	vector <int> cnt_delt(1 << m);
	int mxcnt = 0;
	int mxmask = 1;
	for (int i = 0; i < m; i++) {
		mxmask *= 3;
	}
	for (int mask3 = 0; mask3 < mxmask; mask3++) {
		int cmask3 = mask3;
		int mask2 = 0;
		vector <pair <int, int>> ceds;
		vector <vector <int>> curg(n);
		int ccnt = 0;
		for (int i = 0; i < m; i++) {
			mask2 *= 2;
			if (cmask3 % 3 == 0) {
				mask2++;
				ceds.push_back(eds[i]);
			}
			if (cmask3 % 3 == 1) {
				ceds.push_back(eds[i]);
				ccnt++;
			}
			if (cmask3 % 3 == 2) {
				ceds.push_back({ eds[i].second, eds[i].first });
				ccnt++;
			}
			cmask3 /= 3;
		}
		for (auto [a, b] : ceds) {
			curg[a].push_back(b);
		}
		g = curg;
		for (auto [a, b] : ceds) {
			can[a][b] = check(a, b);
			can[b][a] = check(b, a);
		}
		DSU cdsu(n);
		for (auto [a, b] : ceds) {
			if (can[b][a]) {
				cdsu.merge(a, b);
			}
		}
		int fl = 1;
		for (auto [a, b] : ceds) {
			if ((dsu.get(a) == dsu.get(b)) + (cdsu.get(a) == cdsu.get(b)) == 1) {
				fl = 0;
				break;
			}
		}
		cnt_delt[mask2] = ccnt;
		if (fl) {
			cnt_poss[mask2]++;
		}
	}
	for (int i = 0; i < cnt_poss.size(); i++) {
		if (cnt_poss[i] == 1) {
			mxcnt = max(mxcnt, cnt_delt[i]);
		}
	}
	int cntmask = 0;
	for (int i = 0; i < cnt_poss.size(); i++) {
		if (cnt_delt[i] == mxcnt) {
			cntmask += cnt_poss[i] == 1;
		}
	}
	cout << cntmask << '\n' << mxcnt;
}