Deskripsi Masalah

Anda tersesat ke dalam sebuah rumah besar (mansion). Rumah besar ini memiliki struktur di mana kamar-kamar berbentuk persegi tersusun dalam kisi-kisi ke arah timur-barat dan utara-selatan, dengan $M$ kolom ke arah timur-barat dan $N$ baris ke arah utara-selatan, sehingga totalnya terdapat $M \times N$ kamar. Kamar pada kolom ke-$x$ dari barat ($1 \le x \le M$) dan baris ke-$y$ dari selatan ($1 \le y \le N$) dinyatakan dengan $(x, y)$.

Setiap pasang $2$ kamar yang bersebelahan ke arah timur, barat, selatan, atau utara dihubungkan oleh sebuah pintu yang berada di tengah dinding. Setiap pintu berada dalam salah satu dari dua keadaan: tertutup sehingga tidak dapat dilewati, atau terbuka sehingga dapat dilewati. Ketika pintu terbuka, dibutuhkan waktu $1$ menit untuk berpindah antar bagian tengah kamar-kamar tersebut. Selain itu, di bagian tengah beberapa kamar terdapat sakelar; jika sakelar ditekan terus selama $1$ menit, keadaan buka/tutup dari seluruh pintu di dalam rumah besar akan berganti (berbalik).

Saat ini, semua pintu yang menghubungkan $2$ kamar yang bersebelahan ke arah timur-barat sedang tertutup, dan semua pintu yang menghubungkan $2$ kamar yang bersebelahan ke arah utara-selatan sedang terbuka. Saat ini Anda berada di bagian tengah kamar $(1, 1)$, dan Anda ingin berpindah ke bagian tengah kamar $(M, N)$ dalam waktu sesingkat mungkin.

Tugas

Diberikan ukuran rumah besar $M, N$ serta posisi $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ dari $K$ kamar yang memiliki sakelar, buatlah program untuk mencari berapa menit waktu tersingkat yang diperlukan untuk berpindah dari bagian tengah kamar $(1, 1)$ ke bagian tengah kamar $(M, N)$, dimulai dari keadaan di mana semua pintu yang menghubungkan $2$ kamar bersebelahan arah timur-barat tertutup dan semua pintu yang menghubungkan $2$ kamar bersebelahan arah utara-selatan terbuka. Namun, jika tidak mungkin mencapai kamar $(M, N)$, tunjukkan hal tersebut.

Batasan

• $2 \le M \le 100000$: banyaknya kamar ke arah timur-barat di rumah besar.
• $2 \le N \le 100000$: banyaknya kamar ke arah utara-selatan di rumah besar.
• $1 \le K \le 200000$: banyaknya kamar yang memiliki sakelar.
• $1 \le X_i \le M$: posisi arah timur-barat dari kamar yang memiliki sakelar.
• $1 \le Y_i \le N$: posisi arah utara-selatan dari kamar yang memiliki sakelar.

Masukan

Bacalah data berikut dari masukan standar.

• Pada baris ke-$1$, tertulis bilangan bulat $M, N, K$ yang dipisahkan oleh spasi. $M$ menyatakan banyaknya kamar ke arah timur-barat di rumah besar, $N$ menyatakan banyaknya kamar ke arah utara-selatan di rumah besar, dan $K$ menyatakan banyaknya kamar yang memiliki sakelar.
• Pada baris ke-$i$ ($1 \le i \le K$) dari $K$ baris berikutnya, tertulis bilangan bulat $X_i, Y_i$ yang dipisahkan oleh spasi. Ini menyatakan bahwa terdapat sakelar di bagian tengah kamar $(X_i, Y_i)$. $K$ pasangan $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ saling berbeda satu sama lain.

Keluaran

Cetak ke keluaran standar dalam $1$ baris sebuah bilangan bulat yang menyatakan waktu tersingkat dalam menit yang diperlukan untuk berpindah. Namun, jika tidak mungkin mencapai kamar $(M, N)$, cetak bilangan bulat $-1$ sebagai gantinya.

Kriteria Penilaian

• Untuk $20\%$ dari data penilaian, berlaku $M \le 1000$ dan $N \le 1000$.
• Untuk $30\%$ dari data penilaian, berlaku $K \le 2000$.
• Untuk $50\%$ dari data penilaian, setidaknya salah satu dari $2$ kondisi tersebut terpenuhi. Selain itu, tidak ada data penilaian yang memenuhi kedua ($2$) kondisi tersebut sekaligus.

Contoh 1

Masukan

3 2 1
1 2

Keluaran

4

Penjelasan

Pada contoh ini, Anda dapat berpindah dari bagian tengah kamar $(1, 1)$ ke bagian tengah kamar $(3, 2)$ dalam $4$ menit melalui tindakan berikut, dan ini adalah waktu tersingkat:

• Berpindah ke bagian tengah kamar $(1, 2)$.
• Menekan sakelar di bagian tengah kamar $(1, 2)$.
• Berpindah ke bagian tengah kamar $(2, 2)$.
• Berpindah ke bagian tengah kamar $(3, 2)$.

Keadaan rumah besar pada saat itu ditunjukkan pada gambar di bawah ini. Pada gambar, arah kanan adalah timur, arah atas adalah utara, tanda $\times$ menyatakan posisi Anda, dan tanda $\bigcirc$ menyatakan sakelar.

Contoh 2

Masukan

3 2 1
2 1

Keluaran

-1

Penjelasan

Pada contoh ini, Anda tidak dapat mencapai kamar $(3, 2)$.

Contoh 3

Masukan

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

Keluaran

25

Penjelasan

Pada contoh ini, keadaan awal rumah besar ditunjukkan seperti gambar di bawah ini. Perhatikan bahwa bisa saja terdapat sakelar di bagian tengah kamar $(1, 1)$ atau kamar $(M, N)$.