#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <random>
#include <time.h>
#include <climits>
//#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

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

random_device rd;
mt19937 gen(rd());
uniform_int_distribution <> distr(0, INT_MAX);

//vector<vector<int>> g;
//vector<vector<int>> rev;
vector<int> topo;
vector<bool> used;
//vector<int> col;

void dfstopo(int v, vector<vector<int>> &rev) {
	used[v] = 1;
	for (auto i : rev[v]) {
		if (!used[i])
			dfstopo(i, rev);
	}
	topo.push_back(v);
}

void dfscol(int v, int c, vector<vector<int>> &g, vector<int> &col) {
	col[v] = c;
	for (auto i : g[v]) {
		if (col[i] == -1)
			dfscol(i, c, g, col);
	}
}

int cntbit(int x) {
	int ans = 0;
	while (x > 0) {
		if (x & 1)
			ans++;
		x = x >> 1;
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, gr;
	cin >> n >> m >> gr;
	vector<vector<int>> g(n), rev(n);
	vector<pair<int, int>> e;
	vector<int> col(n, -1);
	used.assign(n, 0);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		rev[b].push_back(a);
		e.push_back({ a, b });
	}
	for (int i = 0; i < n; i++) {
		if (!used[i])
			dfstopo(i, rev);
	}
	/*for (auto i : topo)
		cout << i << " ";*/
	reverse(topo.begin(), topo.end());
	int c = 0;
	for (auto i : topo) {
		if (col[i] == -1) {
			dfscol(i, c, g, col);
			c++;
		}
	}
	//for (auto i : col)
		//cout << i << " ";
	//cout << endl;
	int maxi = -1, cntans = 1;
	for (int mask = 0; mask < (1 << m); mask++) { // 1 - deleted
		int cnt = cntbit(mask);
		int cntgood = 0;
		for (int dir = 0; dir < (1 << cnt); dir++) { // 1 - the direction is changed
			vector<vector<int>> gt(n), rt(n);
			int p = 0;
			for (int i = 0; i < m; i++) {
				if (!(mask & (1 << i))) {
					gt[e[i].first].push_back(e[i].second);
					rt[e[i].second].push_back(e[i].first);
				}
				else {
					if (!(dir & (1 << p))) {
						gt[e[i].first].push_back(e[i].second);
					    rt[e[i].second].push_back(e[i].first);
					}
					else {
						rt[e[i].first].push_back(e[i].second);
						gt[e[i].second].push_back(e[i].first);
					}
					p++;
				}
			}
			used.assign(n, 0);
			topo.clear();
			for (int i = 0; i < n; i++) {
				if (!used[i])
					dfstopo(i, rt);
			}
			reverse(topo.begin(), topo.end());
			vector<int> ct(n, -1);
			c = 0;
			for (auto i : topo) {
				if (ct[i] == -1) {
					dfscol(i, c, gt, ct);
					c++;
				}
			}
			bool wrong = 0;
			for (int i = 0; i < n && wrong == 0; i++) {
				for (int j = i + 1; j < n && wrong == 0; j++) {
					if (col[i] == col[j] && ct[i] != ct[j])
						wrong = 1;
					else if (ct[i] == ct[j] && col[i] != col[j])
						wrong = 1;
				}
			}
			if (wrong == 0)
				cntgood++;
		}
		//if (mask == 42)
			//cout << cntgood << endl;
		if (cntgood == 1) {
			if (cnt > maxi) {
				//cout << mask << "! " << cnt << endl;
				maxi = cnt;
				cntans = 1;
			}
			else if (cnt == maxi)
				cntans++;
		}
	}
	cout << maxi << "\n" << cntans;
}
