AT_agc047_f [AGC047F] Rooks

[problemUrl]: https://atcoder.jp/contests/agc047/tasks/agc047_f 無限に広がるチェス盤上の $ N $ 個の敵ルークの位置 $ (X_i,\ Y_i) $ が与えられます。*\[訳注: ルークは将棋の飛車と似た動きをする駒です。\]* どの二つのルークも、お互いを攻められる位置にはありません (すなわち、一行あたり、または一列あたりのルークの数は一個以下です)。 あなたは、ルークのうち一個をキングに置き換え、キングを繰り返し動かしてできるだけ多くのルークを取ろうとしています。*\[訳注: キングは将棋の王将と似た動きをする駒です。\]* ルークに攻められているマスに入ることはできません。 また、**斜めに移動することで空きマスに移ることもできません** (しかし、斜めに移動することでルークを取ることはできます)。 (つまり、このキングの動きは、斜め四方向に動いて駒を取ることと縦横四方向に動くことができる強化版ポーンのようなものです。) 各ルークについて、そのルークをキングで置き換えた際に取ることのできる最大数のルークを取るために必要な最小手数を求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 200\,000 $ - $ 1\ \leq\ X_i,\ Y_i\ \leq\ 10^6 $ - $ X_i\ \neq\ X_j $ - $ Y_i\ \neq\ Y_j $ - 入力中の値はすべて整数である。 ### Sample Explanation 1 下図を見てください。 ルーク $ 3 $ をキングに置き換えた場合、他のルークを最大で二個取ることができます。 図の赤い経路がこの場合の最適な手順の一つ - ルーク $ 1 $ を取り、右下方向に進み続けてルーク $ 4 $ を取る - です。 ここでの手数は $ 7 $ 手であり、これが出力例の三つ目の数です。 !\[path\](https://img.atcoder.jp/agc047/rooks\_path\_small3.png) \*$ x $ 軸正方向: 右、$ y $ 軸正方向: 上\* ルーク $ 2,\ 5,\ 6 $ のいずれかをキングに置き換えた場合には、他のルークを一個も取ることができません。このとき、最小手数は $ 0 $ です。