
#include <iostream>
#include <limits>
#include <chrono>
#include <random>
#include <iomanip>
#include <algorithm>
#include <chrono>
#include <random>
#include <math.h>
#include <set>
using namespace std;
const int maxn = 2001;
vector <int> gr[maxn];
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
	if (b.first < a.first)swap(a, b);
	if (a.second < b.first)return { -1,-1 };
	return { min(a.first,b.first),max(a.second,b.second) };
}
void solve3(int n, int m,int g) {
	if (m == n - 1) {
		if(g == 3)abort();
		cout << 0 << "\n" << 0;
		return;
	}
	vector <pair<int, int>> vec;
	int cnt = 0;
	for (int i = 0;i < n;i++) {
		for (auto el : gr[i]) {
			cnt++;
		}
	}
	cout << cnt << "\n" << 1;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, g;
	cin >> n >> m >> g;
	for (int i = 0;i < m;i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		if (v != u + 1)gr[u].push_back(v);
	}
	solve3(n, m,g);
}
