동전

시간 제한1초메모리 제한128 MB

요약

N×N 격자에 놓인 N개의 동전을 한 칸씩 옮기되 같은 칸에 겹치지 않게 하면서 각 행과 각 열에 동전이 하나씩 오도록 만드는 최소 이동 횟수를 구한다.

난이도: 어려움10점 중 8점
유형: 수학, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

$N\times N$ 행렬이 주어지고, 정확히 $N$ 개의 칸에 동전이 하나씩 놓여 있다. 이 행렬 위에서 게임을 하는데, 한 번의 턴에 동전 하나를 골라 인접한 칸으로 옮길 수 있다. 두 칸이 인접하다는 것은 변을 공유한다는 뜻이다. 단, 옮기는 동안 어느 순간에도 두 동전이 같은 칸을 차지해서는 안 된다. 모든 행과 모든 열에 동전이 정확히 하나씩 있도록 만드는 것이 목표이며, 가능한 한 적은 턴으로 끝내려고 한다. 필요한 최소 턴 수를 구하시오.

입력

첫째 줄에 $N$ ( $N\leq 200000$ )이 주어진다. 이는 행의 수, 열의 수, 동전의 수이다.

$(i+1)$ 번째 줄에는 $i$ 번째 동전의 초기 행과 열을 나타내는 두 정수 $r_i$ 와 $c_i$ 가 주어진다. 모든 순서쌍 $(r_i,c_i)$ 는 서로 다름이 보장된다.

출력

게임에서 이기기 위해 필요한 최소 턴 수를 하나의 정수로 출력한다.

예제1

예제 1
입력
```
3
2 1
2 2
2 3
```
예상 출력
```
2
```