Джон работает на огромной парковке. Парковка представляется собой прямоугольное поле \(n \times m\), разбитое на \(n \times m\) квадратных позиций размера \(1 \times 1\). Одну из угловых позиций занимает выезд с парковки.
Машин на парковке много и вывести машину не так уж просто. Единственное, что Джон может сделать — это переместить один из автомобилей на соседнюю позицию, если она свободна. Соседними считаются позиции, имеющие общую сторону. Однако задача усложняется наличием на парковке столбов. На позиции, где стоят столбы, нельзя поставить машину. Парковка вся занята машинами и столбами и единственное свободное место — выезд с парковки. Задача Джона — вывести с парковки один из автомобилей. Помогите ему узнать, какое минимальное число действий ему придется совершить.
В первой строке входного файла два целых числа \(n\) и \(m\)
(\(1 \le n, m \le 50\)) — размеры парковки.
Далее следуют \(n\) строк по \(m\) символов в каждой.
Символ «.» означает пустую позицию, единственная
пустая позиция — выезд с парковки.
Символ «#» означает столб. Столбы нельзя перемещать
и на место столба нельзя ставить автомобили.
Символ «c» означает автомобиль.
Символ «X» — автомобиль, который необходимо
вывести с парковки.
Автомобиль считается выведенным, как только он достигает
выезда с парковки.
Гарантируется, что хотя бы одно из чисел \(n\), \(m\) больше единицы
и каждый из символов «.» и «X» встречается во входном
файле ровно один раз.
Символ «.» всегда располагается в верхнем левом углу парковки.
Если машину вывести невозможно, выведите в выходной
файл единственное слово «Impossible».
Иначе в единственной строке выведите единственное число —
минимальное количество действий для вывода автомобиля.
2390 год. В заброшенном метрополитене города N-ска завелась громадная змея-мутант. Она ползает вдоль перегонов между станциями, повергая в ужас случайно забредающих под землю потомков людей. Размеры змеи настолько велики, что иногда голова появляется на той станции, вдоль которой еще ползет какая-то другая часть тела, и змея повергает в ужас сама себя. Чтобы избавиться от этой проблемы, змея поймала вас и потребовала написать для нее программу, которая может ей прокладывать кратчайший маршрут для головы от одной станции до другой, не проползая при этом по станциям, где находятся участки ее тела.
Будем называть маршрутом последовательность станций, каждые две последовательные из которых соединены перегоном.
Все перегоны в метрополитене имеют одинаковую длину, а змея имеет длину в \((l - 0.5)\) перегонов. Змея может ползти вдоль перегонов, переползая с одного на другой на станциях. Змея может ползти вдоль перегона только в один слой, а ее голова не может появляться на станции, если в этот момент по станции проползает другая часть ее тела. Змея умеет ползать только головой вперед.
С точки зрения теории графов метрополитен города N-ска является вершинным кактусом. Это означает, что ни одна станция не лежит на двух различных циклических маршрутах и никакие два перегона не соединяют одну и ту же пару станций, никакой перегон не соединяет станцию саму с собой, от каждой станции до любой другой до появления змеи можно было добраться по перегонам.
По заданным карте метрополитена, начальному положению змеи и станции, на которую змея хочет поместить свою голову, выясните, какое минимальное количество перегонов придется проползти змее.
В первой строке ввода записано два числа \(n\) и \(k\) — количество станций и количество перегонов в метрополитене (\(1 \le n, k \le 100\,000\)). В следующих \(k\) строках записано по два различных целых числа \(a\) и \(b\) — номера станций, соединенных соответствующим перегоном.
В следующей строке записано единственное число \(l\), характеризующее длину змеи. В следующей строке записано \(l + 1\) число: номера станций, на которых лежат последовательные части змеи, начиная с головы, а также номер станции, в перегоне к которой лежит хвост змеи длиной в \(0.5\) перегона. Исходно змея расположена таким образом, что ни в каком перегоне не находится одновременно две различных части змеи и змея не пересекает себя ни на какой станции.
В последней строке записано единственное целое число — станция, на которую змея хочет поместить свою голову.
Если змея сможет выполнить свою задачу, выведите длину пути — количество перегонов, через которые необходимо проследовать голове змеи.
Если задача невыполнима, выведите единственное число \(-1\).