룩 게임

면접 대비

시간 제한2초메모리 제한512 MB

요약

N x N 보드에 놓인 M개의 룩이 같은 행이나 열에서 사이에 아무것도 없을 때 서로 잡을 수 있다. 더 이상 잡을 수 없을 때까지 두었을 때 최소와 최대 잡은 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 유니온 파인드, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

룩 게임은 한 사람이 하는 게임으로, $N \times N$ 격자와 $M$ 개의 룩 말을 사용한다.

룩은 가로 또는 세로로 놓인 빈 칸을 원하는 만큼 지나 이동할 수 있다. 어떤 룩이 다른 룩을 공격할 수 있으면 그 룩을 잡고 그 룩이 있던 칸으로 이동할 수 있다. 룩 게임에서는 흰색과 검은색을 구분하지 않으므로, 모든 룩은 다른 룩을 잡을 수 있다.

처음에 보드에는 $M$ 개의 룩이 있다. 각 차례에 룩 하나가 다른 룩 하나를 잡는다. 플레이어는 어떤 룩도 잡을 수 없을 때까지 잡기를 반복한다. 이 게임의 목표에는 두 가지가 있다. 하나는 잡은 룩의 수를 최소로 하는 것이고, 다른 하나는 최대로 하는 것이다.

이 문제에서는 잡은 룩의 수의 최솟값과 최댓값을 구해야 한다.

입력

첫째 줄에 체스판의 크기 $N$ 과 룩의 수 $M$ 이 주어진다 ( $1 \le N,M \le 1000$ ). 다음 $M$ 개의 줄에 각 룩의 위치가 주어진다. $i$ 번째 줄의 $x_i$ 와 $y_i$ 는 $i$ 번째 룩이 $x_i$ 번째 열, $y_i$ 번째 행에 있다는 뜻이다 ( $1 \le x_i,y_i \le N$ ). 두 룩이 같은 곳에 있는 경우는 없다.

출력

잡은 룩의 수의 최솟값과 최댓값을 공백 하나로 구분해 출력한다.

예제5

예제 1
입력
```
8 3
1 1
1 8
8 8
```
예상 출력
```
1 2
```
예제 2
입력
```
8 4
1 1
1 8
8 8
8 1
```
예상 출력
```
2 3
```
예제 3
입력
```
5 5
1 1
2 2
3 3
4 4
5 5
```
예상 출력
```
0 0
```
예제 4
입력
```
100 1
100 100
```
예상 출력
```
0 0
```

예제 5

입력

예상 출력

7 8