Həzhir - SBJ Cəngəlliklərinin Şahı!#1466
Kral Həzhir SBJ Cəngəlliklərinin şahıdır. Onun qızı isə SBG Cəngəlliklərindədir. Kral Həzhirə bir məktub gəlib, orada yazılıb ki, qızı uşaq dünyaya gətirib. Kral Həzhir nəvəsini görmək üçün çox səbirsizdir, lakin təəssüf ki, bu o qədər də asan deyil.
SBJ və SBG bir meşə ilə ayrılıb. Meşədə çoxlu düşmən var və Kral Həzhir onları görmək istəmir. Əgər kral SBG-yə gedərkən düşmənlər ona hücum etsələr, hər şey faciəvi bitər və kral nə qızını, nə də nəvəsini görə bilər.
Kral Həzhirin öz mühafizə dəstəsi də var: Əmir, Əmir Hüseyn, Nəvid və Kuşa. Əgər Kral Həzhir qızına və nəvəsinə çata bilməsə, onda mühafizə dəstəsinin üzvləri də kral ilə birlikdə həlak olacaqlar. Hörmətli iştirakçılar, xahiş edirəm, onların hamısını qorumağa kömək edin!
Mühafizə dəstəsi düşmənlərin yerlərini bilir, bu da sizin işinizi və Kral Həzhirin səfərini asanlaşdırır. Bəzilərinə qəribə gələ bilər, lakin meşənin forması M \times N ölçülü şahmat taxtası kimidir ( satırların, isə sütunların sayıdır). Kralın düşmənləri at belindədirlər və şahmatdakı at kimi hərəkət edə bilərlər. Kral Həzhir isə şahmat kralı kimi hərəkət edir.
Düşmənlər hərəkətsizdir, yəni tərpənə bilmirlər. Kral, yalnız düşmən tərəfindən tutulmayan və ya hücum edilməyən hüceyrəyə daxil ola bilər; istisna hallarda isə, yəni SBJ və ya SBG qəsrinin hüceyrəsi olarsa, ora daxil ola bilər.
Mühafizə dəstəsi sizdən SBJ-dan SBG-yə ən qısa yolun uzunluğunu tapmağınızı xahiş edir, çünki Kral Həzhir daha gözləyə bilmir.
Birinci sətirdə testlərin sayı (T \leq 100) verilir. Hər testin birinci sətrində ədəd və verilir; burada N, M \leq 100. Sonrakı sətrin hər birində ədəd S = \{'.', 'Z', 'U', 'G'\} çoxluğundan olan simvol verilir. '.' boş hüceyrə deməkdir. 'Z' həmin hüceyrədə düşmən olduğunu bildirir. 'U' SBJ krallığının, 'G' isə SBG krallığının hüceyrəsidir. Hər testdə dəqiq bir SBJ və bir SBG krallıq hüceyrəsi verilir.
Hər test üçün ayrıca sətirdə, əgər Kral Həzhir SBG krallığına çata bilərsə, "Minimal possible length of a trip is L." formatında minimal yol uzunluğunu çap edin və əvəzinə uyğun ədədi yazın. Əgər Kral Həzhir SBG krallığına təhlükəsiz gedə bilmirsə, "No King Hazhir, you can't go now! Don't kill us!" sətrini çap edin.
Nümunə 1