#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
bool assign_max(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

bool dfs(ll v, vector<bool>& used, vector<set<ll>>& arr, ll need) {
	if (v == need) {
		return true;
	}
	used[v] = true;
	for (auto i : arr[v]) {
		if (!used[i]) {
			if (dfs(i, used, arr, need)) {
				return true;
			}
		}
	}
	return false;
}

void solve() {
	ll n, m, g;
	cin >> n >> m >> g;
	vector<set<ll>> to(n);
	vector<pair<ll, ll>> all;
	for (ll i = 0; i < m; i++) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		all.emplace_back(a, b);
		to[a].insert(b);
	}
	ll ans = 0;
	for (auto[a, b] : all) {
		to[a].erase(b);
		vector<bool> used(n, false);
		if (!dfs(b, used, to, a)) {
			ans++;
		}
		to[a].insert(b);
	}
	cout << ans << '\n' << 1 << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}
