AT_nikkei2019_final_c Come Together

[problemUrl]: https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c 縦 $ H $ 行、横 $ W $ 列のマス目があります。 上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と呼ぶことにします。 それぞれのマスには、$ 1 $ つの駒が置いてあります。 ショウさんは、このうち $ K $ 個の駒をマス目上から取り除きました。 $ i $ 番目の取り除いた駒は、マス $ (R_i,C_i) $ にあった駒です。 今からショウさんは、次の操作を $ 0 $ 回以上行います。 - 駒を $ 1 $ つ選び、その駒が現在置かれているマスから、隣接する別のマスへと移動させる。 このとき、移動先のマスに別の駒があっても構わない。 なお、$ 2 $ つのマスが隣接するとは、$ 2 $ つのマスが辺を共有することを意味する。 ショウさんの目的は、マス目上のすべての駒が同じマスに置いてあるようにすることです。 ショウさんが目的を達成するために必要な最小の操作回数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_K $ $ C_K $

マス目上のすべての駒が同じマスに置いてあるようにするために必要な最小の操作回数を出力せよ。

### 制約 - $ 1\ \leq\ H\ \leq\ 10^5 $ - $ 1\ \leq\ W\ \leq\ 10^5 $ - $ 0\ \leq\ K\ \leq\ \min(10^5,H\ \times\ W\ -1) $ - $ 1\leq\ R_i\ \leq\ H $ - $ 1\leq\ C_i\ \leq\ W $ - $ (R_i,C_i)\ \neq\ (R_j,C_j) $ ($ i\neq\ j $) - 入力される値はすべて整数である。 ### Sample Explanation 1 操作を行う前の段階で駒が置かれているマスは、マス $ (1,1) $, $ (1,3) $, $ (2,3) $ の $ 3 $ つです。 次のように $ 3 $ 回操作することで、すべての駒が同じマスに置かれます。 - マス $ (1,1) $ に置いてある駒をマス $ (1,2) $ へ移動させる。 - マス $ (1,2) $ に置いてある駒をマス $ (1,3) $ へ移動させる。 - マス $ (2,3) $ に置いてある駒をマス $ (1,3) $ へ移動させる。 $ 2 $ 回以下の操作で目的を達成することはできないので、$ 3 $ が答えとなります。