eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Хазхир - король джунглей СБУ!

Хазхир - король джунглей СБУ!

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

"Течение шахматной партии можно разделить на три этапа: первый, когда Вы думаете, как получить преимущество, второй, когда Вы считаете, что получили преимущество, и третий... - когда Вы знаете, что уже проиграли!"

Савелий Тартаковер

Король Хазхир - это король джунглей СБУ. Его дочь находится в джунглях СБГ. Король Хазхир получил письмо, в котором сообщается, что его дочь родила ребёнка. Королю очень хочется увидеть своего внука, но, к сожалению, это не так просто.

СБУ и СБГ разделены лесом. В лесу есть много врагов и королю Хазхиру не хочется с ними встречаться. Если они сумеют атаковать короля по его дороге в СБГ, всё завершится летальным исходом и, естественно, король никогда не увидит свою дочь и внука.

У короля Хазкира есть и своя служба безопасности: Амир, Амир Хусейн, Навид и Куша. Если король Хазхир не сумеет увидеть свою дочь и внука, то вместе с ним погибнут и члены его службы безопасности. Пожалуйста, помогите им всем остаться в живых, уважаемые участники контеста!

Команда безопасности располагает информацией о местонахождении врагов, что облегчает Вашу задачу и жизнь короля Хазхира. Кому то это может показаться странным, но лес имеет вид шахматной доски размером M×N (M - это количество строк, а N - количество столбцов). Враги короля находятся на лошадях и перемещаются они прыжками точно так же, как ходит конь в настоящих шахматах. Король СБУ может перемещаться точно так же, как это делает шахматный король..

Враги являются неподвижными. Король может заходить в любую клетку леса X, если она не занята врагами, или не находится под прицелом врагов, за исключением того случая, когда клетка X является королевским домом СБУ или СБГ.

Служба безопасности попросила Вашей помощи найти длину L кратчайшего пути от СБУ к СБЛ, так как король Хазхир уже не может больше ждать.

Входные данные

Первая строка содержит количество тестов T100. Первая строка каждого теста содержит 2 числа M и N, где N, M100. Последующие M строк содержат каждая по N символов множества S = {'.', 'Z', 'U', 'G'}. '.' обозначены свободные клетки. 'Z' обозначает клетку, занятую врагами. 'U' обозначен королевский дом СБУ и 'G' обозначает королевский дом СБГ. Во всех тестах содержится по одному королевскому дому СБУ и СБГ.

Выходные данные

Выведите длину L для каждого теста в отдельной строке в виде "Minimal possible length of a trip is L." если король Хазхир может добраться до СБГ. Естественно, значение "L" должно быть заменено соответствующим числовым значением. Если король Хазхир не сможет добраться безопасно до СБГ, выведите в соответствующей строке сообщение "No King Hazhir, you can't go now! Don't kill us!"

Пример

Входные данные #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.
Выходные данные #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.