Хазхір - SBU-nun cəngəlliklər kralı!
"Şahmat oyununun gedişatını üç mərhələyə bölmək olar: birinci, üstünlük qazanmaq haqqında düşündüyünüz zaman, ikinci, üstünlük qazandığınızı düşündüyünüz zaman və üçüncü... - artıq uduzduğunuzu bildiyiniz zaman!"
Saveliy Tartakover
Kral Xazhir - SBU cəngəlliklərinin kralıdır. Onun qızı SBG cəngəlliklərindədir. Kral Xazhirə qızının uşaq dünyaya gətirdiyini bildirən bir məktub gəlib. Kral nəvəsini görmək üçün çox istəyir, amma təəssüf ki, bu o qədər də asan deyil.
SBU və SBG meşə ilə ayrılır. Meşədə çoxlu düşmən var və kral Xazhir onlarla qarşılaşmaq istəmir. Əgər onlar kralı SBG-yə gedən yolda hücum edə bilsələr, hər şey ölümcül nəticələnəcək və əlbəttə ki, kral heç vaxt qızını və nəvəsini görə bilməyəcək.
Kral Xazhirin öz təhlükəsizlik xidməti də var: Amir, Amir Hüseyn, Navid və Kuşa. Əgər kral Xazhir qızını və nəvəsini görə bilməsə, onunla birlikdə təhlükəsizlik xidmətinin üzvləri də həlak olacaq. Xahiş edirik, hörmətli müsabiqə iştirakçıları, onların hamısının sağ qalmasına kömək edin!
Təhlükəsizlik komandası düşmənlərin yerini bilir, bu da sizin işinizi və kral Xazhirin həyatını asanlaşdırır. Bəzi insanlara qəribə gələ bilər, amma meşə M×N ölçüsündə bir şahmat taxtası şəklindədir (M - bu sətirlərin sayı, N - sütunların sayı). Kralın düşmənləri atların üstündədir və onlar həqiqi şahmatda atın hərəkət etdiyi kimi tullanaraq hərəkət edirlər. SBU kralı isə şahmat kralı kimi hərəkət edə bilər.
Düşmənlər hərəkətsizdir. Kral meşənin X hücrəsinə daxil ola bilər, əgər o, düşmənlər tərəfindən tutulmayıbsa və ya düşmənlərin hədəfində deyilsə, istisna olmaqla, X hücrəsi SBU və ya SBG kral evlərindən biri olduqda.
Təhlükəsizlik xidməti SBU-dan SBG-yə ən qısa yolun uzunluğunu L tapmaq üçün sizin köməyinizi istəyib, çünki kral Xazhir daha çox gözləyə bilmir.
Giriş verilənləri
Birinci sətir testlərin sayı T ≤ 100 göstərir. Hər testin birinci sətiri M və N ədədlərini ehtiva edir, burada N, M ≤ 100. Növbəti M sətir hər biri N simvoldan ibarət S = {'.', 'Z', 'U', 'G'} çoxluğundan ibarətdir. '.' boş hücrələri göstərir. 'Z' düşmənlərin tutduğu hücrəni göstərir. 'U' SBU kral evini və 'G' SBG kral evini göstərir. Bütün testlərdə bir SBU və bir SBG kral evi var.
Çıxış verilənləri
Hər test üçün L uzunluğunu ayrı-ayrı sətirdə "Minimal possible length of a trip is L." şəklində çıxarın, əgər kral Xazhir SBG-yə çata bilsə. Müvafiq olaraq, "L" dəyəri uyğun ədədi dəyər ilə əvəz olunmalıdır. Əgər kral Xazhir SBG-yə təhlükəsiz çata bilməzsə, müvafiq sətirdə "No King Hazhir, you can't go now! Don't kill us!" mesajını çıxarın.