#ifdef LOCAL
#pragma optimize("", off)
#include "localstd1.h"
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/allocator.h>
#pragma GCC target("avx2,bmi,bmi2")
#include <bits/stdc++.h>
#endif

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

#define all(a) (a).begin(), (a).end()

struct Node {
	vector<int> e;
	int vers = -1;
};
vector<Node> graph, rgraph;
vector<pair<int, int>> edges;

int get_to(int from, int i, bool rev) {
	pair<int, int> e = edges[i];
	if (rev) swap(e.first, e.second);
	return e.first == from ? e.second : -1;
}

void dfsr(int u, int vers) {
	if (rgraph[u].vers == vers) {
		return;
	}
	rgraph[u].vers = vers;
	for (int i : rgraph[u].e) {
		int to = get_to(u, i, true);
		if (to == -1) continue;
		dfsr(to, vers);
	}
}

void dfs(int u, int vers) {
	if (graph[u].vers == vers) {
		return;
	}
	graph[u].vers = vers;
	for (int i : graph[u].e) {
		int to = get_to(u, i, false);
		if (to == -1) continue;
		dfs(to, vers);
	}
}

vector<int> split() {
	int vers = 0;
	int n = graph.size();
	for (int i = 0; i < n; i++) graph[i].vers = rgraph[i].vers = -1;
	vector<int> res(n, -1);
	for (int i = 0; i < n; i++) {
		if (res[i] == -1) {
			dfs(i, vers);
			dfsr(i, vers);
			for (int j = 0; j < n; j++) if (graph[j].vers == vers && rgraph[j].vers == vers) {
				res[j] = vers;
			}
			vers++;
		}
	}
	return res;
}

vector<int> partit;

pair<int, int> solve() {
	int n = graph.size(), m = edges.size();

	int mx = 0, cnt = 1;
	for (int mask = 1; mask < 1 << m; mask++) {
		vector<int> inds;
		for (int i = 0; i < m; i++) {
			if (mask & (1 << i)) {
				inds.push_back(i);
			}
		}
		int k = inds.size();
		int curcnt = 0;
		for (int mask1 = 0; mask1 < 1 << k; mask1++) {

			for (int i = 0; i < k; i++) {
				if (mask1 & (1 << i)) {
					swap(edges[inds[i]].first, edges[inds[i]].second);
				}
			}

			auto p1 = split();
			if (partit == p1) {
				curcnt++;
			}

			for (int i = 0; i < k; i++) {
				if (mask1 & (1 << i)) {
					swap(edges[inds[i]].first, edges[inds[i]].second);
				}
			}

			if (curcnt > 1) break;
		}
		if (curcnt == 1) {
			if (mx < bitset<32>(mask).count()) {
				mx = bitset<32>(mask).count();
				cnt = 1;
			}
			else if (mx == bitset<32>(mask).count()) {
				cnt++;
			}
		}
	}

	return { mx, cnt };
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, g; cin >> n >> m >> g;
	graph.assign(n, {});
	rgraph.assign(n, {});
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v; u--; v--;
		edges.push_back({ u, v });
		graph[u].e.push_back(edges.size() - 1);
		graph[v].e.push_back(edges.size() - 1);
		rgraph[v].e.push_back(edges.size() - 1);
		rgraph[u].e.push_back(edges.size() - 1);
	}
	partit = split();
	auto [mx, cnt] = solve();
	cout << mx << '\n' << cnt;

	return 0;
}