AT_joi2013ho3 現代的な屋敷 (Modern Mansion)

[problemUrl]: https://atcoder.jp/contests/joi2013ho/tasks/joi2013ho3 あなたは，ある大きな屋敷に迷い込んでしまった．この屋敷は正方形の部屋が東西南北に格子状に，東西方向に $ M $ 列，南北方向に $ N $ 行の合計 $ M\ \times\ N $ 個並んだ構造をしている．西から $ x $ 列目 ($ 1\ \leqq\ x\ \leqq\ M $)，南から $ y $ 行目 ($ 1\ \leqq\ y\ \leqq\ N $) にある部屋を $ (x,\ y) $ で表す． 東西南北に隣り合う $ 2 $ 部屋の間は，壁の中央にある扉により結ばれている．それぞれの扉は，閉じていて通行不可能な状態か，開いていて通行可能な状態のいずれかにある．扉が開いているとき，それらの部屋の中央間を移動するのに $ 1 $ 分間かかる．また，いくつかの部屋の中央にはスイッチがあり，スイッチを $ 1 $ 分間押し続けると，屋敷内のすべての扉の開閉の状態が切り替わる． 今，東西に隣り合う $ 2 $ 部屋を結ぶすべての扉は閉じていて，南北に隣り合う $ 2 $ 部屋を結ぶすべての扉は開いている．あなたは今部屋 $ (1,\ 1) $ の中央にいて，部屋 $ (M,\ N) $ の中央まで最短時間で移動したい．

標準入力から以下のデータを読み込め． - $ 1 $ 行目には，整数 $ M,\ N,\ K $ が空白を区切りとして書かれている．$ M $ は屋敷の東西方向の部屋の個数，$ N $ は屋敷の南北方向の部屋の個数，$ K $ はスイッチのある部屋の個数を表す． - 続く $ K $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ K $) には，整数 $ X_i,\ Y_i $ が空白を区切りとして書かれている．これは，部屋 $ (X_i,\ Y_i) $ の中央にスイッチがあることを表す．$ K $ 個の組 $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ \ldots,\ (X_K,\ Y_K) $ は互いに異なる．

標準出力に，移動に最短で何分かかるかを表す整数を $ 1 $ 行で出力せよ．ただし，部屋 $ (M,\ N) $ に辿り着くことができないときは代わりに整数 $ -1 $ を出力せよ．

### 課題 屋敷の大きさ $ M,\ N $ および，スイッチのある $ K $ 個の部屋の位置 $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ \ldots,\ (X_K,\ Y_K) $ が与えられる．東西に隣り合う $ 2 $ 部屋を結ぶすべての扉は閉じていて，南北に隣り合う $ 2 $ 部屋を結ぶすべての扉は開いている状態から始めて，部屋 $ (1,\ 1) $ の中央から部屋 $ (M,\ N) $ の中央まで移動するのに最短で何分かかるかを求めるプログラムを作成せよ．ただし，部屋 $ (M,\ N) $ に辿り着くことができないときはそれを指摘せよ． ### 制限 $ 2\ \leqq\ M\ \leqq\ 100\,000 $ 屋敷の東西方向の部屋の個数$ 2\ \leqq\ N\ \leqq\ 100\,000 $ 屋敷の南北方向の部屋の個数$ 1\ \leqq\ K\ \leqq\ 200\,000 $ スイッチのある部屋の個数$ 1\ \leqq\ X_i\ \leqq\ M $ スイッチのある部屋の東西方向の位置$ 1\ \leqq\ Y_i\ \leqq\ N $ スイッチのある部屋の南北方向の位置- - - - - - ### 採点基準 採点用データのうち，配点の $ 20 $ %分については，$ M\ \leqq\ 1\,000 $，$ N\ \leqq\ 1\,000 $ を満たす． 採点用データのうち，配点の $ 30 $ %分については，$ K\ \leqq\ 2\,000 $ を満たす． 採点用データのうち，配点の $ 50 $ %分については，これら $ 2 $ つの条件の少なくとも一方を満たす．また，これら $ 2 $ つの条件の両方を満たすような採点用データはない． - - - - - - ### Sample Explanation 1 この例では，以下の行動によって $ 4 $ 分間で部屋 $ (1,\ 1) $ の中央から部屋 $ (3,\ 2) $ の中央へ移動することができ，これが最短である． - 部屋 $ (1,\ 2) $ の中央へ移動する． - 部屋 $ (1,\ 2) $ の中央のスイッチを押す． - 部屋 $ (2,\ 2) $ の中央へ移動する． - 部屋 $ (3,\ 2) $ の中央へ移動する． このときの屋敷の様子が以下の図に表されている．図では右方向が東，上方向が北であり，×印はあなたの位置，○印はスイッチを表す． !\[088a24305fc2470b9ff17a0cd60c556b.png\](https://img.atcoder.jp/joi2013ho/088a24305fc2470b9ff17a0cd60c556b.png) - - - - - - ### Sample Explanation 2 この例では，あなたは部屋 $ (3,\ 2) $ に辿り着くことができない． - - - - - - ### Sample Explanation 3 この例では，最初の屋敷の様子は以下の図のようになっている．部屋 $ (1,\ 1) $ や部屋 $ (M,\ N) $ の中央にスイッチがある可能性もあることに注意せよ． !\[128c91a07269803fa720723600260cea.png\](https://img.atcoder.jp/joi2013ho/128c91a07269803fa720723600260cea.png)