Rooks Game

Interview

Time limit2sMemory limit512 MB

Summary

Given M rooks on an N x N board, a rook captures another when they share a row or column with nothing between them; find the minimum and maximum number of captures before no captures remain.

Level: Medium6 of 10
Topics: Graph, Union-find, Greedy, Implementation
Solved: No attempts yet

Problem

Rooks Game is a single-player game played on an $N \times N$ board with $M$ rook pieces.

A rook moves any number of unoccupied squares horizontally or vertically. When a rook can attack another rook, it can capture that rook and move to the square the rook occupied. In Rooks Game, white and black are not distinguished, so every rook can capture any other rook.

Initially, there are $M$ rooks on the board. In each move, one rook captures another rook. The player repeats captures until no rook can be captured. The game has two goals. One is to minimize the number of captured rooks, and the other is to maximize it.

In this problem, you must find the minimum and maximum values of the number of captured rooks.

Input

The first line contains two integers $N$ and $M$ , the size of the board and the number of rooks ( $1 \le N,M \le 1000$ ). Each of the following $M$ lines gives the position of one rook. The $i$ -th line contains $x_i$ and $y_i$ , meaning the $i$ -th rook is in column $x_i$ and row $y_i$ ( $1 \le x_i,y_i \le N$ ). No two rooks are in the same place.

Output

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

Examples5

Example 1
Input
```
8 3
1 1
1 8
8 8
```
Expected output
```
1 2
```
Example 2
Input
```
8 4
1 1
1 8
8 8
8 1
```
Expected output
```
2 3
```
Example 3
Input
```
5 5
1 1
2 2
3 3
4 4
5 5
```
Expected output
```
0 0
```
Example 4
Input
```
100 1
100 100
```
Expected output
```
0 0
```

Example 5

Input

Expected output

7 8