Problem: Problem Statement

"Rooks Game" is a single-player game and uses a chessboard which has $N \times N$ grid and $M$ rook pieces.

A rook moves through any number of unoccupied squares horizontally or vertically. When a rook can attack another rook, it can capture the rook and move to the square which was occupied. Note that, in Rooks Game, we don't distinguish between white and black, in other words, every rook can capture any of other rooks.

<image>

Initially, there are $M$ rooks on the board. In each move, a rook captures another rook. The player repeats captures until any rook cannot be captured. There are two types of goal of this game. One is to minimize the number of captured rooks, and the other is to maximize it.

In this problem, you are requested to calculate the minimum and maximum values of the number of captured rooks.

* * *

Input

The input consists of a single test case in the format below.

> $N$ $M$ $x_{1}$ $y_{1}$ $\vdots$ $x_{M}$ $y_{M}$

The first line contains two integers $N$ and $M$ which are the size of the chessboard and the number of rooks, respectively ($1 \le N, M \le 1000$). Each of the following $M$ lines gives the position of each rook. The $i$-th line with $x_{i}$ and $y_{i}$ means that the $i$-th rook is in the $x_{i}$-th column and $y_{i}$-th row ($1 \le x_{i}, y_{i} \le N$). You can assume any two rooks are not in the same place.

Output

Output the minimum and maximum values of the number of captured rooks separated by a single space.

Examples

Input| Output
---|---


8 3
1 1
1 8
8 8


|


1 2



8 4
1 1
1 8
8 8
8 1


|


2 3



5 5
1 1
2 2
3 3
4 4
5 5


|


0 0



100 1
100 100


|


0 0



10 12
1 2
1 4
1 6
3 6
5 6
10 7
8 7
6 7
4 7
2 7
7 3
9 5


|


7 8






Example

Input




Output

Solution (in CPP):

Solution:
//・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;
}