Məsələlər
Хазхир - король джунглей СБУ!
Хазхир - король джунглей СБУ!
\textit{"Течение шахматной партии можно разделить на три этапа: первый, когда Вы думаете, как получить преимущество, второй, когда Вы считаете, что получили преимущество, и третий... - когда Вы знаете, что уже проиграли!"}
\textit{Савелий Тартаковер}
Король Хазхир - это король джунглей СБУ. Его дочь находится в джунглях СБГ. Король Хазхир получил письмо, в котором сообщается, что его дочь родила ребёнка. Королю очень хочется увидеть своего внука, но, к сожалению, это не так просто.
СБУ и СБГ разделены лесом. В лесу есть много врагов и королю Хазхиру не хочется с ними встречаться. Если они сумеют атаковать короля по его дороге в СБГ, всё завершится летальным исходом и, естественно, король никогда не увидит свою дочь и внука.
У короля Хазкира есть и своя служба безопасности: Амир, Амир Хусейн, Навид и Куша. Если король Хазхир не сумеет увидеть свою дочь и внука, то вместе с ним погибнут и члены его службы безопасности. Пожалуйста, помогите им всем остаться в живых, уважаемые участники контеста!
Команда безопасности располагает информацией о местонахождении врагов, что облегчает Вашу задачу и жизнь короля Хазхира. Кому то это может показаться странным, но лес имеет вид шахматной доски размером \textbf{M}×\textbf{N} (\textbf{M} - это количество строк, а \textbf{N} - количество столбцов). Враги короля находятся на лошадях и перемещаются они прыжками точно так же, как ходит конь в настоящих шахматах. Король СБУ может перемещаться точно так же, как это делает шахматный король..
\includegraphics{https://static.e-olymp.com/content/f3/f30e892d190a9b36a8fe88c78e92c605c3c9dcff.jpg}
Враги являются неподвижными. Король может заходить в любую клетку леса \textbf{X}, если она не занята врагами, или не находится под прицелом врагов, за исключением того случая, когда клетка \textbf{X} является королевским домом СБУ или СБГ.
Служба безопасности попросила Вашей помощи найти длину \textbf{L} кратчайшего пути от СБУ к СБЛ, так как король Хазхир уже не может больше ждать.
\InputFile
Первая строка содержит количество тестов \textbf{T} ≤ \textbf{100}. Первая строка каждого теста содержит \textbf{2} числа \textbf{M} и \textbf{N}, где \textbf{N}, \textbf{M} ≤ \textbf{100}. Последующие \textbf{M} строк содержат каждая по \textbf{N} символов множества \textbf{S} = \{'\textbf{.}', '\textbf{Z}', '\textbf{U}', '\textbf{G}'\}. '\textbf{.}' обозначены свободные клетки. '\textbf{Z}' обозначает клетку, занятую врагами. '\textbf{U}' обозначен королевский дом СБУ и '\textbf{G}' обозначает королевский дом СБГ. Во всех тестах содержится по одному королевскому дому СБУ и СБГ.
\OutputFile
Выведите длину \textbf{L} для каждого теста в отдельной строке в виде "\textbf{Minimal possible length of a trip is L.}" если король Хазхир может добраться до СБГ. Естественно, значение "\textbf{L}" должно быть заменено соответствующим числовым значением. Если король Хазхир не сможет добраться безопасно до СБГ, выведите в соответствующей строке сообщение "\textbf{No King Hazhir, you can't go now! Don't kill us!}"
Giriş verilənləri #1
4 5 5 .Z..G ..Z.. Z...Z .Z... U.... 3 2 ZG .Z UZ 6 5 ....G ..... ..... ..Z.. ..... U..Z. 3 3 ZZ. ... UG.
Çıxış verilənləri #1
No King Hazhir, you can't go now! Don't kill us! Minimal possible length of a trip is 2. No King Hazhir, you can't go now! Don't kill us! Minimal possible length of a trip is 1.