
#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) };
}
int cnt = 0;
void dfs(int u, vector <int>& color) {
	color[u] = 1;
	for (auto el : gr[u]) {
		if (!color[el]) {
			dfs(el, color);
			cnt++;
		}
	}
	color[u] = 2;
}
void solve3(int n, int m,int g) {
	vector <int> color(n, 0);
	for (int i = 0;i < n;i++) {
		if (!color[i]) {
			dfs(i, color);
		}
	}
	
	cout << m - 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--;
		gr[u].push_back(v);
	}
	solve3(n, m,g);
}
