23720번 - 움얌얌

무한한 크기의 체스판에 $N$ 개의 룩(Rook)이 있다. 룩은, 같은 행이나 같은 열에 있는 말을 공격할 수 있다. 초기 상태에서는, 한 룩이 다른 룩을 공격할 수 없음이 보장된다. 다시 말해, 모든 룩은 다른 행에 있고, 모든 룩은 다른 열에 있다.

당신은 이 중 하나의 룩을 구재현 코치 로 대체할 수 있다. 구재현 코치는 4방향으로 (상하좌우) 인접한 셀로 움직일 수 있으나, 룩에 공격 당하는 위치 (즉, 어떠한 룩과 같은 행이나 같은 열에 있는) 로는 움직일 수 없다.

또한 구재현 코치는 맛있는 음식을 좋아한다. 만약 구재현 코치가 위치한 셀에서 8방향으로 (상하좌우 및 대각선) 인접한 다른 셀에 룩이 있다면, 구재현 코치는 해당 룩의 위치로 움직일 수 있으며, 그 후 그 룩을 맛있게 먹어버린다. 룩에 공격 당하는 것보다 룩을 먹는 것이 우선적으로 적용된다.

구재현 코치는 가능한 많은 룩을 먹으려고 하며, 이러한 방법이 여러가지이면 그 중 최소의 움직임으로 최대한의 룩을 먹으려고 한다.

모든 룩들에 대해서, 해당 룩을 구재현 코치 로 대체했을 때, 최대한의 룩을 먹기 위해 구재현 코치가 움직이는 횟수의 최솟값을 출력하라.

첫 번째 줄에 룩의 수 $N$ 이 주어진다. ($2 \le N \le 200\,000$)

이후 $N$개의 줄에 각 룩의 좌표 $X_i, Y_i$ 가 주어진다. ($1 \le X_i, Y_i \le 10^6$)

모든 룩은 다른 행과 다른 열에 있다. 다시 말해, $i \neq j$ 일 경우 $X_i \neq X_j, Y_i \neq Y_j$ 가 성립한다.

$N$개의 줄에 걸쳐 하나의 정수를 출력하라. $i$ 번째 줄에는, $i$ 번째 룩을 구재현 코치로 대체했을 때, 최대한의 룩을 먹기 위해 구재현 코치가 움직이는 횟수의 최솟값을 출력하라.