Хазхир - король джунглей СБУ!
Хазхир - король джунглей СБУ!
"Течение шахматной партии можно разделить на три этапа: первый, когда Вы думаете, как получить преимущество, второй, когда Вы считаете, что получили преимущество, и третий... - когда Вы знаете, что уже проиграли!"
Савелий Тартаковер
Король Хазхир - это король джунглей СБУ. Его дочь находится в джунглях СБГ. Король Хазхир получил письмо, в котором сообщается, что его дочь родила ребёнка. Королю очень хочется увидеть своего внука, но, к сожалению, это не так просто.
СБУ и СБГ разделены лесом. В лесу есть много врагов и королю Хазхиру не хочется с ними встречаться. Если они сумеют атаковать короля по его дороге в СБГ, всё завершится летальным исходом и, естественно, король никогда не увидит свою дочь и внука.
У короля Хазкира есть и своя служба безопасности: Амир, Амир Хусейн, Навид и Куша. Если король Хазхир не сумеет увидеть свою дочь и внука, то вместе с ним погибнут и члены его службы безопасности. Пожалуйста, помогите им всем остаться в живых, уважаемые участники контеста!
Команда безопасности располагает информацией о местонахождении врагов, что облегчает Вашу задачу и жизнь короля Хазхира. Кому то это может показаться странным, но лес имеет вид шахматной доски размером M×N (M - это количество строк, а N - количество столбцов). Враги короля находятся на лошадях и перемещаются они прыжками точно так же, как ходит конь в настоящих шахматах. Король СБУ может перемещаться точно так же, как это делает шахматный король..
Враги являются неподвижными. Король может заходить в любую клетку леса X, если она не занята врагами, или не находится под прицелом врагов, за исключением того случая, когда клетка X является королевским домом СБУ или СБГ.
Служба безопасности попросила Вашей помощи найти длину L кратчайшего пути от СБУ к СБЛ, так как король Хазхир уже не может больше ждать.
Входные данные
Первая строка содержит количество тестов T ≤ 100. Первая строка каждого теста содержит 2 числа M и N, где N, M ≤ 100. Последующие 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!"
Пример
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.
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.