Хазір — правитель джунглів SBJ!#1466
Король Хазір — правитель джунглів SBJ. Його донька знаходиться в джунглях SBG. Король Хазір отримав листа, що його донька народила дитину. Король Хазір дуже прагне побачити свого онука, але, на жаль, це зовсім не так просто.
SBJ та SBG розділяє ліс. У лісі багато ворогів, і король Хазір не хоче з ними зіткнутися. Якщо вони нападуть на короля по дорозі в SBG, усе закінчиться трагічно, і король більше ніколи не побачить свою доньку чи онука.
Король Хазір також має власну команду охорони: Амір, Амір Хоссейн, Навід і Куша. Якщо король Хазір не дістанеться до доньки й онука, члени охорони також загинуть разом із ним. Допоможіть їм усім залишитися в безпеці, дорогі учасники!
Команда охорони знає розташування ворогів, що спрощує ваше завдання й подорож короля Хазіра. Це може здатися дивним, але ліс має форму шахової дошки розміру M \times N ( — кількість рядків, — кількість стовпців). Вороги короля їздять верхи на конях і ходять, як шахові коні. Король Хазір пересувається, як шаховий король.
Вороги стоять на місці й не рухаються. Король може стати в клітинку , якщо вона не зайнята або не атакована ворогами, окрім випадків, коли є клітинкою королівств SBJ чи SBG.
Команда охорони просить вас знайти довжину найкоротшого шляху від SBJ до SBG, адже король Хазір чекати більше не може.
У першому рядку міститься кількість тестів (T \leq 100). У першому рядку кожного тесту задано числа і , де N, M \leq 100. Далі йде рядків по символів із множини S = \{'.', 'Z', 'U', 'G'\}. '.' означає порожню клітинку. 'Z' — клітинка, зайнята ворогом. 'U' — королівство SBJ, 'G' — королівство SBG. У кожному тесті рівно по одній клітинці з королівствами SBJ й SBG.
Для кожного тесту в окремому рядку виведіть довжину у форматі:
Minimal possible length of a trip is .
якщо король Хазір може дістатися до королівства SBG. Замість вкажіть відповідне число. Якщо король Хазір не може безпечно дістатися до SBG, виведіть:
No King Hazhir, you can't go now! Don't kill us!
Приклад 1