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

const int maxm = 1 << 20;
bool can[maxm];
int sz[maxm];
int n, m;
std::vector<std::pair<int, int>> e;
std::vector<std::vector<int>> g, s;
std::vector<int> used, cl, tp, cl2;
int color = 0;
int ans = 0;
void dfs(int i) {
	used[i] = 1;
	for (int to : s[i]) {
		if (!used[to]) {
			dfs(to);
		}
	}
	tp.push_back(i);
}
void dfs2(int i) {
	cl[i] = color;
	for (int to : g[i]) {
		if (cl[to] == -1) {
			dfs2(to);
		}
	}
}

void dfs_m(int i) {
	used[i] = 1;
	for (int to : s[i]) {
		if (!used[to]) {
			dfs(to);
		}
	}
	tp.push_back(i);
}
void dfs2_m(int i) {
	cl2[i] = color;
	for (int to : g[i]) {
		if (cl2[to] == -1) {
			dfs2_m(to);
		}
	}
}
bool check(int mask) {
	tp.clear();
	cl2.assign(n, -1);
	s.assign(n, {});
	g.assign(n, {});
	used.assign(n, 0);
	for (int i = 0; i < m; ++i) {
		if ((mask >> i) & 1) {
			s[e[i].first].push_back(e[i].second);
			g[e[i].second].push_back(e[i].first);
		}
		else {
			s[e[i].second].push_back(e[i].first);
			g[e[i].first].push_back(e[i].second);
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			dfs_m(i);
		}
	}
	color = 0;
	for (int i = n - 1; i >= 0; --i) {
		if (cl2[tp[i]] == -1) {
			dfs2_m(tp[i]);
			++color;
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if ((cl[i] == cl[j] && cl2[i] != cl2[j]) || (cl2[i] == cl2[j] && cl[i] != cl[j])) {
				return 0;
			}
		}
	}
	return 1;
}
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int t;
	std::cin >> n >> m >> t;
	e.resize(m);
	g.resize(n);
	s.resize(n);
	used.resize(n);
	cl.resize(n, -1);
	for (auto& i : e) {
		std::cin >> i.first >> i.second;
		--i.first;
		--i.second;
		g[i.first].push_back(i.second);
		s[i.second].push_back(i.first);
	}
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			dfs(i);
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		if (cl[tp[i]] == -1) {
			dfs2(i);
			++color;
		}
	}
	std::vector<int> ans(m + 1);
	ans[0] = 1;
	for (int mask = 1; mask < (1 << m); ++mask) {
		sz[mask] = sz[mask & (mask - 1)] + 1;
		if (mask == 12) {
			mask = mask;
		}
		if (can[mask] || check(mask)) {
			for (int i = 0; i < m; ++i) {
				can[mask | (1 << i)] = 1;
			}
		}
		else {
			if (sz[mask] == 3) {
				mask = mask;
			}
			++ans[sz[mask]];
		}
	}
	for (int i = m; i >= 0; --i) {
		if (ans[i] > 0) {
			std::cout << i << '\n' << ans[i] << '\n';
			return 0;
		}
	}
}
/*
4 5 1
1 2
2 3
3 4
4 1
1 3

*/