//・M - 連結成分数 (Hint: 全域木, 葉から)
//・うく
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef pair<int, int> P;

//Dinic (嘘実装なのでTLEするかも…)
const int VMAX = 2500;
struct Edge {
	int from, to, flow, rev;
	Edge(int from, int to, int flow, int rev) {
		this->from = from;
		this->to   = to;
		this->flow = flow;
		this->rev  = rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &g, int from, int to, int flow) {
	//cout << "add_edge(" << from << ", " << to << ", " << flow << ")" << endl;
	g[from].push_back(Edge(from, to, flow, g[to].size()));
	g[to].push_back(Edge(to, from, 0, g[from].size() - 1));
}

int dfs(Graph &g, int s, int t, int flow, bool yet[], int level[]) {
	yet[s] = false;
	if (s == t) return flow;
	for (int i = 0; i < g[s].size(); i++) {
		int v = g[s][i].to;
		if (g[s][i].flow > 0 && yet[v] && level[v] == level[s] + 1) {
			int res = dfs(g, v, t, min(flow, g[s][i].flow), yet, level);
			if (res > 0) {
				int r = g[s][i].rev;
				g[s][i].flow -= res;
				g[v][r].flow += res;
				return res;
			}
		}
	}
	return 0;
}

int maxflow(Graph &g, int s, int t) {
	const int INF_DIST = 11451419;
	const int INF_FLOW = 11451419;
	int level[VMAX];
	bool yet[VMAX];
	queue<int> que;
	int i;
	int ret = 0;
	
	while (true) {
		for (i = 0; i < g.size(); i++) level[i] = INF_DIST;
		que.push(s); level[s] = 0;
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (i = 0; i < g[v].size(); i++) {
				int nv = g[v][i].to;
				if (g[v][i].flow > 0 && level[nv] > level[v] + 1) {
					que.push(nv);
					level[nv] = level[v] + 1;
				}
			}
		}
		if (level[t] >= INF_DIST) break;
					
		while (true) {
			for (i = 0; i < g.size(); i++) yet[i] = true;
			int flow = dfs(g, s, t, INF_FLOW, yet, level);
			if (flow == 0) break;
			ret += flow;
		}
	}
	return ret;
}

//
int n, m;
int x[1000], y[1000];
vector<P> xs[1000];
vector<P> ys[1000];
vector<int> et[1000];

int main() {
	int i, j;
	
	cin >> n >> m;
	rep(i, m) {
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
		xs[x[i]].push_back(P(y[i], i));
		ys[y[i]].push_back(P(x[i], i));
	}
	rep(i, n) {
		sort(xs[i].begin(), xs[i].end());
		sort(ys[i].begin(), ys[i].end());
	}
	
	rep(i, n) {
		rep(j, (int)xs[i].size() - 1) {
			int u = xs[i][j].second;
			int v = xs[i][j + 1].second;
			et[u].push_back(v);
			et[v].push_back(u);
		}
	}
	
	rep(i, n) {
		rep(j, (int)ys[i].size() - 1) {
			int u = ys[i][j].second;
			int v = ys[i][j + 1].second;
			et[u].push_back(v);
			et[v].push_back(u);
		}
	}
	
	bool used[1000] = {false};
	int cnt = 0;
	rep(i, m) {
		if (used[i]) continue;
		
		queue<int> que;
		que.push(i);
		used[i] = true;
		while (!que.empty()) {
			int v = que.front();
			que.pop();
			rep(j, et[v].size()) {
				int nv = et[v][j];
				if (!used[nv]) {
					used[nv] = true;
					que.push(nv);
				}
			}
		}
		cnt++;
	}
	
	//最大流
	Graph g;
	g.resize(2 * n + 2);
	rep(i, n) { add_edge(g, 0, i + 1, 1); }
	rep(i, m) {
		add_edge(g, x[i] + 1, y[i] + 1 + n, 1);
	}
	rep(i, n) { add_edge(g, i + 1 + n, 2 * n + 1, 1); }
	
	int flow = maxflow(g, 0, 2 * n + 1);
	
	cout << m - flow << " " << m - cnt << endl;
	return 0;
}


Measured memory_bytes: 3500