Kazino
Düzbucaqlı sahənin yuxarı sol küncündə ölçüləri N×M olan bir oyun kubu yerləşdirilib və onun açılımı şəkildə göstərilmişdir. Kub elə istiqamətlənib ki, ön tərəfi birə, sol tərəfi isə iki rəqəminə uyğun gəlir. Sahənin hüceyrələri kvadrat şəklindədir və onların ölçüləri kubun tərəflərinin ölçüləri ilə eynidir.
Kub sahə boyunca hərəkət edə bilər, bir kənarından aşaraq aşağı, yuxarı, sağa və ya sola bitişik hüceyrəyə keçə bilər. Məsələn, başlanğıc vəziyyətindən kub sağa hərəkət edərsə, ön tərəfi iki rəqəminə uyğun gələcək, aşağı hərəkət edərsə üç rəqəminə uyğun gələcək. Kub sahənin sərhədlərindən kənara çıxa bilməz.
CASINO proqramını yazın ki, sahə haqqında məlumat əsasında kubun yuxarı sol küncdən sahənin aşağı sağ küncünə bir mümkün yolunu tapsın. Bu zaman elə bir yol tapmaq lazımdır ki, kubun son hüceyrədəki ön tərəfi mümkün olan ən böyük qiymətə malik olsun. Kub sahənin hər bir hüceyrəsini bir neçə dəfə ziyarət edə bilər.
Giriş verilənləri
Giriş faylının ilk sətiri sahənin hündürlüyünü və enini müəyyən edən iki natural ədəd N və M (2 ≤ N, M ≤ 50) ehtiva edir. Daha sonra sahə N sətirlə verilir, hər biri M ədədindən ibarətdir, hər biri 0 və ya 1 bərabərdir. Sahənin hüceyrəsinə 1 uyğun gəldikdə, kub həmin hüceyrəni ziyarət edə bilməz. Əks halda, bu hüceyrə kubun yolunda ola bilər. Başlanğıc hüceyrəyə həmişə 0 uyğun gəlir.
Çıxış verilənləri
Çıxış faylının ilk sətiri tapılmış yolun uzunluğunu göstərən natural ədəd W olmalıdır. Daha sonra faylda W sətir olmalıdır, hər biri sahənin cari addımda hüceyrəsinin koordinatını göstərir. Koordinat sahənin hüceyrəsinin sətir və sütun nömrəsindən ibarət olan natural ədədlər cütlüyüdür.
Əgər axtarılan yol mövcud deyilsə, çıxış faylı -1 ədədini ehtiva edən bir sətir olmalıdır.