#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <assert.h>
using namespace std;

//#define int long long
#define ll long long
#define vi vector<int>
#define pi pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define vpi vector<pi>
#define vvi vector<vi>
#define gb(a, b) (((a) >> (b)) & 1)

struct snm {
	vi par;
	vi sz;
	snm(int n = 0) {
		par.assign(n, 1);
		sz.assign(n, 1);
		for (int i = 0; i < n; i++) par[i] = i;
	}
	int get(int i) {
		if (par[i] == i) return i;
		int x = get(par[i]);
		par[i] = x;
		return x;
	}
	vi getall() {
		vi ans(par.size());
		for (int i = 0; i < par.size(); i++) {
			ans[i] = get(i);
		}
		return ans;
	}
	void unite(int i, int j) {
		i = get(i);
		j = get(j);
		if (i == j) return;
		if (i > j) swap(i, j);
		par[i] = j;
		sz[j] += sz[i];
	}
};

vi used;
vi par;
snm sm;
void dfs(vvi& graph, int u) {
	used[u] = 1;
	for (int v : graph[u]) {
		if (used[v] == 1) {
			int x = u;
			while (x != v) {
				sm.unite(x, par[x]);
				x = par[x];
			}
		}
		else if (!used[v]) {
			par[v] = u;
			dfs(graph, v);
		}
	}
	used[u] = 2;
}

int cnt(int mask) {
	int ans = 0;
	while (mask) {
		ans += ((mask % 2));
		mask /= 2;
	}
	return ans;
}
bool cmp(int a, int b) {
	return cnt(a) > cnt(b);
}


signed main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int n, m, g;
	cin >> n >> m >> g;
	vvi graph(n, vi());
	vpi edg(m);
	int m3 = 1;
	for (int i = 0; i < m; i++) {
		m3 *= 3;
		cin >> edg[i].ff >> edg[i].ss;
		edg[i].ff--;
		edg[i].ss--;
		graph[edg[i].ff].push_back(edg[i].ss);
	}
	sm = snm(n);
	par.assign(n, 0);
	used = vi(n);
	for (int i = 0; i < n; i++) {
		if (!used[i]) dfs(graph, i);
	}
	vi tt = sm.getall();
	int ans = -1;
	int anssp = 0;
	for (int mask = 0; mask < (1 << m); mask++) {
		
		int tm = mask;
		vpi tedg;
		for (int i = 0; i < m; i++) {
			if (!gb(mask, i)) {
				//ngraph[edg[i].ff].push_back(edg[i].ss);
			}
			else {
				tedg.push_back(edg[i]);
			}
		}
		if (mask == 63) {
			int mat = 322;
		}
		int spp = 0;
		for (int tmask = 0; tmask < (1 << tedg.size()); tmask++) {
			vvi ngraph(n);
			sm = snm(n);
			par.assign(n, 0);
			used = vi(n);

			for (int i = 0; i < m; i++) {
				if (!gb(mask, i)) {
					ngraph[edg[i].ff].push_back(edg[i].ss);
				}
				else {
					//tedg.push_back(edg[i]);
				}
			}

			int i = 0;
			for (pi el : tedg) {
				int u = el.ff;
				int v = el.ss;
				if (gb(tmask, i)) {
					swap(u, v);
				}
				ngraph[u].push_back(v);
				i++;
			}
			for (int i = 0; i < n; i++) {
				if (!used[i]) dfs(ngraph, i);
			}
			vi tx = sm.getall();
			if (tmask == 63) {
				int mat = 322;
			}
			if (tx == tt) {
				spp++;
			}
		}
		if (spp == 1) {
			if (cnt(mask) == ans) {
				anssp++;
			}
			else {
				if (cnt(mask) > ans) {
					anssp = 1;
					ans = cnt(mask);
				}
			}
		}
	}
	cout << ans << endl;
	cout << anssp << endl;
}
