#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

void solve();

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cout << fixed << setprecision(30);
	int t = 1; 
	// cin >> t;
	while (t--) {
		solve();
	}
}

const int N = 2020;
pair<int, int> ed[N];

int calc_cmps(int n, int m) {
	vector<vector<int>> g(n);
	for (int i = 0; i < m; i++) {
		g[ed[i].x].push_back(ed[i].y);
	}
	vector<int> ts, used(n, 0);
	auto top_sort {[&](auto top_sort, int s) -> void {
		used[s] = 1;
		for (int i : g[s]) {
			if (!used[i]) {
				top_sort(top_sort, i);
			}
		}
		ts.push_back(s);
	}};
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			top_sort(top_sort, i);
		}
	}
	vector<vector<int>> h(n);
	vector<int> col(n, -1);
	for (int i = 0; i < m; i++) {
		h[ed[i].y].push_back(ed[i].x);
	}
	auto paint {[&](auto paint, int s, int c) -> void {
		col[s] = c;
		for (int i : h[s]) {
			if (col[i] == -1) {
				paint(paint, i, c);
			}
		}
	}};
	int ans = 0;
	reverse(all(ts));
	for (int i : ts) {
		if (col[i] == -1) {
			paint(paint, i, ans++);
		}
	}
	return ans;
}

int dsu[N];

int get(int x) {
	return dsu[x] == x ? x : dsu[x] = get(dsu[x]);
}

void merge(int x, int y) {
	dsu[get(y)] = get(x);
}

void solve() {
	int n, m, gg;
	cin >> n >> m >> gg;
	iota(dsu, dsu + n, 0);
	int need = n;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v; u--; v--;
		ed[i] = {u, v};
	}
	int cmps = calc_cmps(n, m), ans = 0;
	// cout << cmps << '\n';
	for (int i = 0; i < m; i++) {
		if (get(ed[i].x) == get(ed[i].y)) continue;
		if ((ed[i].x + 1) % n != ed[i].y) continue;
		int old = ed[i].y;
		ed[i].y = ed[i].x;
		if (calc_cmps(n, m) > cmps) {
			merge(ed[i].x, ed[i].y);
			ans++;
			cmps++;
		} else {
			ed[i].y = old;
		}
	}
	cout << ans << '\n' << 1 << '\n';
}
