002 - 現代的な屋敷

時間制限 1 秒 / メモリ制限 256 MB / 得点 100 / x 0 /


TLE
1sec
MLE
256MB
得点
100

問題

あなたは,ある大きな屋敷に迷い込んでしまった.この屋敷は正方形の部屋が東西南北に格子状に, 東西方向に 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個の部屋の位置 ( X1 , Y1 ), ( X2 , Y2 ) , …, ( XK , YK ) が与えられる.東西に隣り合う 2 部屋を結ぶ すべての扉は閉じていて,南北に隣り合う 2 部屋を結ぶすべての扉は開いている状態から始めて,部屋 ( 1 , 1 ) の中央から部屋 ( M , N ) の中央まで移動するのに最短で何分かかるかを求める プログラムを作成せよ. ただし,部屋 ( M , N )に辿り着くことができないときはそれを指摘せよ.

制限

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

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

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

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

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

入力

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

  • 1 行目には,整数 M , N , K が空白を区切りとして書かれている. M は屋敷の東西方向の部屋の個数, N は屋敷の南北方向の部屋の個数,K は スイッチのある部屋の個数を表す.
  • 続く K 行のうちの i 行目 (1 ≤ iK ) には, 整数 Xi , Yi が空白を区切りとして書かれている. これは,部屋 ( Xi , Yi ) の中央にスイッチがあることを表す. K 個の組 ( X1 , Y1 ), ( X2 , Y2 ) , …, ( XK , YK )は互いに異なる.

出力

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

採点基準

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

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

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

入出力例

入力例1 出力例1
3 2 1
1 2
 
4

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

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

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


入力例2 出力例2
3 2 1
2 1
 
-1

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

入力例3 出力例3
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) の中央にスイッチがある可能性もあることに注意せよ.