#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>
#include <random>




struct Edge {
	int to, pair;
	bool has_flow;
};
std::vector<std::vector<Edge>> make_graph(const int size, const std::vector<std::pair<int, int>>& edges) {
	std::vector<std::vector<Edge>> result(size);
	for (const auto& pair : edges) {
		result[pair.first].push_back(Edge{ pair.second, (int)result[pair.second].size(), true });
		result[pair.second].push_back(Edge{ pair.first, (int)result[pair.first].size() - 1, false });
	}
	return result;
}
static std::vector<std::vector<Edge>> graph;
static std::vector<int> depth;
static std::vector<int> searching;
void set_depth(const int source) {
	depth.assign(depth.size(), -1);
	depth[source] = 0;
	std::queue<int> queue; queue.push(source);
	while (!queue.empty()) {
		const auto top = queue.front(); queue.pop();
		for (const auto& edge : graph[top]) if (edge.has_flow && depth[edge.to] == -1) {
			depth[edge.to] = depth[top] + 1;
			queue.push(edge.to);
		}
	}
}
bool push_flow(const int current, const int sink) {
	if (current == sink) return true;
	while (searching[current] < graph[current].size()) {
		const auto edge = graph[current][searching[current]];
		if (edge.has_flow && depth[current] < depth[edge.to] && push_flow(edge.to, sink)) {
			graph[current][searching[current]].has_flow = false;
			graph[edge.to][edge.pair].has_flow = true;
			return true;
		}
		++searching[current];
	}
	return false;
}
int max_flow(const int source, const int sink) {
	depth = std::vector<int>(graph.size());
	searching = std::vector<int>(graph.size(), 0);
	int flow = 0;
	bool has_flow = true;
	while (has_flow) {
		has_flow = false;
		set_depth(source);
		searching.assign(searching.size(), 0);
		while (push_flow(source, sink)) {
			has_flow = true;
			++flow;
		}
	}
	return flow;
}
class UnionFind {
	std::vector<int> vec;
public:
	UnionFind(int size) : vec(size, -1) {};
	int find(int a) {
		if (vec[a] < 0) return a;
		return vec[a] = find(vec[a]);
	}
	bool same(int a, int b) {
		return find(a) == find(b);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (vec[a] > vec[b]) std::swap(a, b);
		vec[a] += vec[b];
		vec[b] = a;
	}
};
int main() {
	int n, m; std::cin >> n >> m;
	std::vector<std::pair<int, int>> edges;
	std::vector<bool> row(n, false), column(n, false);
	UnionFind uft((n << 1) + 1);
	for (auto i = 0; i < m; ++i) {
		int x, y; std::cin >> x >> y;
		edges.emplace_back(x - 1, (n << 1) + i);
		edges.emplace_back((n << 1) + i, n + y - 1);
		uft.unite(x - 1, n + y - 1);
		row[y - 1] = true;
		column[x - 1] = true;
	}
	for (auto i = 0; i < n; ++i) {
		edges.emplace_back((n << 1) + m, i);
		edges.emplace_back(n + i, (n << 1) + m + 1);
	}
	graph = make_graph((n << 1) + m + 2, edges);
	const int flow = max_flow((n << 1) + m, (n << 1) + m + 1);
	int min = 0;
	for (auto i = 0; i < n; ++i) {
		if (column[i] && !uft.same(i, n << 1)) {
			++min;
			uft.unite(i, n << 1);
		}
		if (row[i] && !uft.same(n + i, n << 1)) {
			++min;
			uft.unite(n + i, n << 1);
		}
	}
	std::cout << (m - flow) << ' ' << (m - min) << '\n';
}


Measured memory_bytes: 3336