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

#define int long long

using namespace std;

vector<int>v;

int get(int u) {
	if (v[u] == u) {
		return u;
	}
	v[u] = get(v[u]);
	return v[u];
}

void add(int a, int b) {
	a = get(a);
	b = get(b);
	v[a] = b;
}

int32_t main() {
	int n, m, g;
	cin >> n >> m >> g;
	v.resize(n);
	for (int i = 0; i < n; ++i) {
		v[i] = i;
	}
	vector<pair<int, int>>lol;
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		lol.push_back({ x,y });
	}
	sort(lol.begin(), lol.end());
	reverse(lol.begin(), lol.end());
	int cnt = 0;
	for (int i = 0; i < m; ++i) {
		if (get(lol[i].first) == get(lol[i].second)) {
			cnt++;
		}
		else {
			add(lol[i].first, lol[i].second);
		}
	}
	cout << cnt << '\n' << 1;
	return 0;
}