#include <iostream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

int get(int u, int p, vector<vector<pair<int,int>>>& v,vector<int>&used) {
	used[u] = 1;
	int cnt = 0;
	for (pair<int,int> y : v[u]) {
		int x = y.second;
		if (x != p) {
			if (x < p) {
				if (used[x] == 1) {
					cnt++;
				}
			}
			else {
				if (used[x] != 2) {
					cnt += get(x, u, v, used);
				}
			}
		}
	}
	used[u] = 2;
	return cnt;
}




int32_t main() {
	int n, m, g;
	cin >> n >> m >> g;
	vector<vector<pair<int,int>>>v(n);
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		v[x].push_back({ 1,y });
		v[y].push_back({ 2, x });
	}
	vector<int>used(n);
	for (int i = 0; i < n; ++i) {
		sort(v[i].begin(), v[i].end());
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (used[i] == 0) {
			ans += get(i, i, v, used);
		}
	}
	cout << ans << '\n' << 1;
	return 0;
}