Qəribə Strəlyandsk Səyahəti

Avropa Gənclər İnformatika Olimpiadası 2542-ci ildə Strəlyandiyada keçirilir. Strəlyandiya m sətir (sıfırdan m - 1-ə qədər nömrələnmiş) və n sütundan (sıfırdan n - 1-ə qədər nömrələnmiş) ibarət bir cədvəl formasındadır, hər hüceyrədə bir şəhər yerləşir. Gəlin (r, c) hüceyrəsini r sətirində və c sütununda yerləşən hüceyrə kimi təyin edək. İştirakçıların qaldığı yataqxana (0, 0) hüceyrəsində, yarış zalı isə (m - 1, n - 1) hüceyrəsində yerləşir.

Strəlyandiyanın xüsusiyyəti ondadır ki, bəzi şəhərlərdə böyük oxlar var. Bir əməliyyatla oxu saat əqrəbi istiqamətində 90 dərəcə döndərmək olar. Başlanğıcda hər bir ox şimal, şərq, cənub və ya qərb istiqamətini göstərir. Olimpiada təşkilatçıları iştirakçıların naviqasiyası üçün ölkələrinin bu xüsusiyyətindən istifadə etmək istəyirlər.

Olimpiada iştirakçıları oxlar üzrə hərəkət edəcəklər. Hər bir şəhərdən onlar oxun istiqamətində qonşu şəhərə keçəcəklər. Əgər onlar ox olmayan bir şəhərə düşsələr və ya Strəlyandiyanın sərhədlərindən kənara çıxsalar, onlar itəcək və olimpiadada iştirak edə bilməyəcəklər. Yarış təşkilatçıları istəyirlər ki, bütün iştirakçılar yataqxanadan (hüceyrə (0, 0)) yarış zalına (hüceyrə (m - 1, n - 1)) uğurla çatsınlar. Bunun üçün onlar bəzi oxları döndərə bilərlər. Onlara məqsədə çatmaq üçün lazım olan minimal döndərmə sayını müəyyən etməyə kömək edin və ya iştirakçıların oxların hər hansı istiqamətində yarış zalına çata bilməyəcəyini bildirin.

Giriş Məlumatları

Birinci sətir iki tam ədəd m və n (1 ≤ ​ n, m ​ ≤ 500) - sətir və sütun sayını ehtiva edir. Növbəti m sətir hər biri n simvolu olan oxların başlanğıc istiqamətini təyin edir (N - şimal, E - şərq, S - cənub, W - qərb, X - ox yoxdur). Sonuncu sətirin son simvolu (yəni yarış zalına uyğun simvol) həmişə X olacaq. N simvolu "yuxarı", E simvolu "sağa", S simvolu "aşağı", və W simvolu "sola" istiqamətini göstərir. Hər bir hüceyrə aşağıdakı simvollardan birini ehtiva edir: N, E, S, W, X.

Çıxış Məlumatları

Təşkilatçıların etməli olduğu ox döndərmələrinin minimal sayını çıxarın. Əgər həll mövcud deyilsə, -1 çıxarın.

Birinci nümunə üçün izahlar

Optimal həll - (1, 2) hüceyrəsindəki W-ni S-ə dəyişməkdir, oxu üç dəfə döndərərək.

İkinci nümunə üçün izahlar

Burada heç nə etmək lazım deyil, iştirakçılar onsuz da yarış zalına çatacaqlar.

Üçüncü nümunə üçün izahlar

(0, 0) hüceyrəsindəki oxu bir dəfə döndərmək (S əldə etmək üçün), (1, 0) hüceyrəsindəki oxu iki dəfə döndərmək (E əldə etmək üçün), və (2, 1) hüceyrəsindəki oxu bir dəfə döndərmək (E əldə etmək üçün).