004 - 現代的な屋敷

問題

あなたは，ある大きな屋敷に迷い込んでしまった．この屋敷は正方形の部屋が東西南北に格子状に， 東西方向に M 列，南北方向に N 行の合計 M × N 個並んだ構造をしている． 西から x 列目 ( 1 ≤ x ≤ M ) ， 南から y 行目 ( 1 ≤ x ≤ N ) ， にある部屋を ( x , y ) で表す．

東西南北に隣り合う 2 部屋の間は，壁の中央にある扉により結ばれている．それぞれの扉は，閉じてい て通行不可能な状態か，開いていて通行可能な状態のいずれかにある．扉が開いているとき，それらの部 屋の中央間を移動するのに 1 分間かかる．また，いくつかの部屋の中央にはスイッチがあり，スイッチを 1 分間押し続けると，屋敷内のすべての扉の開閉の状態が切り替わる．

今，東西に隣り合う 2 部屋を結ぶすべての扉は閉じていて，南北に隣り合う 2 部屋を結ぶすべての扉は開いている． あなたは今部屋 ( 1 , 1 ) の中央にいて，部屋 ( M , N ) の中央まで最短時間で移動したい．

課題

屋敷の大きさ M , N および，スイッチのあるK個の部屋の位置 ( X₁ , Y₁ ), ( X₂ , Y₂ ) , …, ( X_K , Y_K ) が与えられる．東西に隣り合う 2 部屋を結ぶ すべての扉は閉じていて，南北に隣り合う 2 部屋を結ぶすべての扉は開いている状態から始めて，部屋 ( 1 , 1 ) の中央から部屋 ( M , N ) の中央まで移動するのに最短で何分かかるかを求める プログラムを作成せよ． ただし，部屋 ( M , N )に辿り着くことができないときはそれを指摘せよ．

制限

2 ≤ M ≤ 100,000 屋敷の東西方向の部屋の個数

2 ≤ N ≤ 100,000 屋敷の南北方向の部屋の個数

1 ≤ K ≤ 200,000 スイッチのある部屋の個数

1 ≤ X_i ≤ M スイッチのある部屋の東西方向の位置

1 ≤ Y_i ≤ N スイッチのある部屋の南北方向の位置

入力

標準入力から以下のデータを読み込め．

• 1 行目には，整数 M , N , K が空白を区切りとして書かれている． M は屋敷の東西方向の部屋の個数， N は屋敷の南北方向の部屋の個数，K は スイッチのある部屋の個数を表す．
• 続く K 行のうちの i 行目 (1 ≤ i ≤ K ) には， 整数 X_i , Y_i が空白を区切りとして書かれている． これは，部屋 ( X_i , Y_i ) の中央にスイッチがあることを表す． K 個の組 ( X₁ , Y₁ ), ( X₂ , Y₂ ) , …, ( X_K , Y_K )は互いに異なる．

出力

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

採点基準

採点用データのうち，配点の 20% 分については，M ≤ 1,000 ，N ≤ 1,000 を満たす．

採点用データのうち，配点の 30% 分については，K ≤ 2,000 を満たす．

採点用データのうち，配点の 50% 分については，これら 2 つの条件の少なくとも一方を満たす． また，これら 2 つの条件の両方を満たすような採点用データはない．

入出力例

3 2 1
1 2

4

この例では，以下の行動によって 4 分間で部屋 ( 1 , 1 ) の中央から部屋 ( 3 , 2 ) の中央へ移動することができ， これが最短である．

1. 部屋 ( 1 , 2 ) の中央へ移動する．
2. 部屋 ( 1 , 2 ) の中央のスイッチを押す．
3. 部屋 ( 2 , 2 ) の中央へ移動する．
4. 部屋 ( 3 , 2 ) の中央へ移動する．

このときの屋敷の様子が以下の図に表されている．図では右方向が東，上方向が北であり，×印はあな たの位置，○印はスイッチを表す．

3 2 1
2 1

-1

この例では，あなたは部屋 ( 3 , 2 ) に辿り着くことができない．

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

25

この例では，最初の屋敷の様子は以下の図のようになっている．部屋 (1, 1) や部屋 (M, N) の中央にスイッチがある可能性もあることに注意せよ．