#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

//#include <ext/pb_ds/assoc_containe.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template <class T> order_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find_by_orede, order_of_key

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

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")


const int inf = 1e18;

void ans(int t) {
	if (t) cout << "First\n";
	else cout << "Second\n";
	exit(0);
}


vector<vector<int>> g;

bool connect(int u, int i, int j) {
	if (u == j) return 1;
	if (u > j) return 0;

	if (u == i) {
		bool f1 = 0;
		for (int v : g[u])
			if (v == j) f1 = 1;
		if (!f1) return 0;
	}

	for (int v : g[u])
		if (!(u == i && v == j))
			if (connect(v, i, j)) return 1;

	return 0;
}
void solve() {
	int n, m; cin >> n >> m;
	g.resize(n);

	int G; cin >> G;
	if (G == 3) {
		cout << m - (n - 1) << '\n' << 1;
		return;
	}
	if (G == 4) {
		for (int i = 0; i < m; ++i) {
			int u, v; cin >> u >> v;
			u--; v--;
			g[u].push_back(v);
		}
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (connect(i, i, j)) ++cnt;
			}
		}
		cout << cnt << '\n' << 1;
		return;
	}
	cout << n << ' ' << 1;
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int t = 1; //cin >> t;
	while (t--) solve();
}