Evakuasiya

Dramatik hadisələr baş verir – köhnə hörümçək öz düzbucaqlı torunda oturmuşdu, birdən torun bəzi yerləri yanmağa başladı. Xoşbəxtlikdən, uzaqgörən hörümçək özünü xilas edə biləcəyi xüsusi bir qəfəs hazırlamışdı. İndi onun vəzifəsi bu qəfəsə çatmaqdır və o, ən təhlükəsiz yolu seçməyə çalışır.

Tor düzbucaqlı bir şəbəkədir, koordinatları (1, 1) - (a, b) arasında dəyişir. Yanğın nöqtələri məlumdur. Hörümçəyin başlanğıc mövqeyi – (1, 1), evakuasiya nöqtəsi isə (a, b) nöqtəsində yerləşir. Hörümçək şəbəkənin kənarı boyunca hərəkət edir və hər bir hərəkət 1 saniyə çəkir, yanğın isə t saniyəyə yayılır. Hörümçək yanan zirvədə dayana bilməz.

Yolun təhlükəsi anlayışını təqdim edək. Bəzi yolu nəzərdən keçirək. Zirvəni təhlükəli adlandıracağıq, əgər bu zirvədən keçərkən ona bitişik olan zirvələrdən ən azı biri yanırsa. Yolun təhlükəsi onun içindəki təhlükəli zirvələrin sayıdır. Hörümçək özünə maksimum təhlükəsizlik təmin etmək istəyir. Ona kömək edin!

Giriş məlumatları

Birinci sətirdə a və b (1 ≤ a, b ≤ 500) - torun ölçüləri verilir. Növbəti sətirdə t (1 ≤ t ≤ 100) sayı verilir. Daha sonra k (1 ≤ k ≤ a * b) - yanğın nöqtələrinin sayı verilir. Növbəti k sətirdə iki ədəd - yanan zirvələrin koordinatları verilir.

Çıxış məlumatları

(1, 1) nöqtəsindən (a, b) nöqtəsinə gedən yolun minimal təhlükəsini çıxarın. Əgər belə bir yol yoxdursa, "-1" çıxarın.

İzah

Birinci halda hörümçək yolu (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) → (4, 3) ilə gedir. Əvvəlcə təhlükəli olan hüceyrə (1, 1) olur, çünki onun yanında yanan (2, 1) var. Hörümçək (1, 2) hüceyrəsində olanda, hələ də yalnız (2, 1) hüceyrəsi yanır, buna görə də (1, 2) təhlükəsizdir. Hörümçək (1, 3) hüceyrəsinə çatanda, daha üç hüceyrə yanır - (1, 1), (2, 2), (3, 1), amma yananlardan heç biri (1, 3) ilə bitişik deyil – buna görə də o təhlükəsizdir. Daha sonra hörümçək (2, 3) hüceyrəsindədir, (2, 2) hüceyrəsi yanır, deməli (2, 3) təhlükəlidir. Hörümçək (3, 3) hüceyrəsinə gələndə, daha çox hüceyrə yanır: (1, 2), (2, 3), (3, 2), (4, 1). Görünür ki, (3, 3) (3, 2) ilə bitişikdir, o artıq yanır, deməli (3, 3) təhlükəlidir. Növbəti hərəkətlə hörümçək (4, 3) hüceyrəsində olanda, yeni hüceyrələr yanmır (hələ iki saniyə keçməyib), yananlardan heç biri (4, 3) ilə bitişik deyil. Müvafiq olaraq, yolun təhlükəsi 3-ə bərabərdir (üç təhlükəli zirvə – (1, 1), (2, 3) və (3, 3)). Hörümçək heç bir başqa yolla yanmayan hüceyrələrdən keçmədən gedə bilməz.

İkinci halda üç saniyədən sonra (4, 3) zirvəsi yanır, hörümçək üç saniyəyə ora çatmağa vaxt tapmayacaq.