現代的な屋敷(Modern Mansion)

あなたは，ある大きな屋敷に迷い込んでしまった．この屋敷は正方形の部屋が東西南北に格子状に，東西方向に M 列，南北方向に N 行の合計 M × N 個並んだ構造をしている．西から x 列目(1 ≤ x ≤ M)，南から y 行目(1 ≤ y ≤ 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) に辿り着くことができないときはそれを指摘せよ．

制限

入力

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

出力

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

採点基準

入出力例

入力例 1

3 2 1
1 2

出力例 1

4

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

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

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



入力例 2

3 2 1
2 1

出力例 2

-1

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


入力例 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

出力例 3

25

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


問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。