#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) x.begin(),x.end()
#define mem(x, y) memset(x, y, sizeof x)
#define sz(x) int(x.size())
#define int ll

const int maxn = 2008, MOD = 1e9 + 7;
vector <int> g[maxn], inv[maxn];
int dp[maxn][maxn]; // к-во способов попасть u->v
bool used[maxn];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int n, m, group;
	cin >> n >> m >> group;
	// group == {3, 4}
	
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		inv[v].push_back(u);
	}
	
	for (int i = 1; i <= n; i++) {
		dp[i][i] = 1;
		for (int j = i + 1; j <= n; j++) {
			for (int v: inv[j]) dp[i][j] = min(dp[i][j] + dp[i][v], 2LL);
			//cout << i << " " << j << ": " << dp[i][j] << '\n';
		}
	}
	
	int ans = 0;
	for (int v = 1; v <= n; v++) {
		for (int u : g[v]) {
			if (dp[v][u] > 1) ans++;
		}
	}
	cout << ans << '\n' << 1 << '\n';
	
	return 0;
}

/*

5 6 13
1 2
2 3
2 4
3 4
3 5
4 5

*/
