#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>

using namespace std;
using ll = long long;
using ld = long double;
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("Ofast")
const ll INF = 1e9 + 7;
template<typename T>
void input(vector<T>& arr, size_t size) {
	arr.resize(size);
	for (T& i : arr) {
		cin >> i;
	}
}
template<typename T>
void print(vector<T>& arr) {
	for (T& i : arr) {
		cout << i << ' ';
	}
	cout << '\n';
}

vector<vector<int>> g,gr;
vector<int> tp, used;
int tr = 1;
void top(int u) {
	used[u] = tr;
	for (auto i : g[u]) {
		if (used[i] < tr) {
			top(i);
		}
	}
	tp.push_back(u);
}
void dfs(int u, vector<int>& c, int val) {
	c[u] = val;
	for (auto i : gr[u]) {
		if (!c[i]) {
			dfs(i, c, val);
		}
	}
}


void con(vector<int>& c) {
	fill(all(c), 0);
	tp.clear();
	fill(all(used), 0);
	int n = c.size(), val = 1;
	for (size_t i = 0; i < n; i++)
	{
		if (!used[i]) {
			top(i);
		}
	}
	reverse(all(tp));
	for (auto i : tp)
	{
		if (c[i])continue;
		dfs(i, c, val++);
	}
}



void solve() {
	int n, m, gp;
	cin >> n >> m >> gp;
	g.resize(n);
	gr.resize(n);
	used.resize(n);
	vector<pair<int, int>> e;
	vector<int> c(n),p(n);
	for (size_t i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		--a; --b;
		e.push_back({ a,b });
		g[a].push_back(b);
		gr[b].push_back(a);
	}
	if (gp == 3) {
		cout << m - n << " 1";
		return;
	}
	con(c);
	vector<bool> dp(1 << m, 0);
	dp[0] = 1;
	for (size_t i = 1; i < (1 << m); i++)
	{
		g.assign(n, vector<int>(0));
		gr.assign(n, vector<int>(0));
		for (size_t j = 0; j < m; j++)
		{
			int a = e[j].first, b = e[j].second;
			if ((i >> j) & 1) {
				swap(a, b);
			}
			g[a].push_back(b);
			gr[b].push_back(a);
		}
		con(p);
		vector<int> rc(n + 1, -1),nw(n + 1,-1);
		bool f = 0;
		for (size_t i = 0; i < n; i++)
		{
			if (nw[p[i]] == -1) {
				nw[p[i]] = c[i];
			}
			else if (nw[p[i]] != c[i]) {
				f = 1;
				break;
			}
			if (rc[c[i]] == -1) {
				rc[c[i]] = p[i];
			}
			else if (rc[c[i]] != p[i]) {
				f = 1;
				break;
			}
		}
		dp[i] = f;
	}
	vector<int> ans(m + 1);
	for (size_t i = 0; i < (1 << m); i++)
	{
		for (size_t j = 0; j < m; j++)
		{
			if ((i >> j) & 1) {
				dp[i] = dp[i] && dp[i ^ (1 << j)];
			}
			if (!dp[i]) {
				break;
			}
		}
		if (!dp[i]) {
			continue;
		}
		int cnt = 0;
		
		for (size_t j = 0; j < m; j++)
		{
			cnt += ((i >> j) & 1);
		}
		if (cnt == 3) {
#ifdef _DEBUG
			//cout << i << ' ';
#endif // _DEBUG
		}
		ans[cnt] += 1;
	}
	for (int i = ans.size() - 1; i >= 0; i--)
	{
		if (ans[i] != 0) {
			cout << i << '\n' << ans[i];
			break;
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("in.txt", "r", stdin);
#endif // _DEBUG
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt = 1;
#ifdef _DEBUG
	cin >> tt;
#endif // _DEBUG
	while (tt--)
	{
		solve();
#ifdef _DEBUG
		cout << "\n================\n";
#endif // _DEBUG
	}
}