< На список задач
      

Задача I. Быстрая доставка на Клиаанд

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 Mb

После очередной победы над врагами Специального Корпуса прошло несколько дней. Джим и Ангелина начали наслаждаться отдыхом в разных уголках Галактики, но их снова собирает Лига. Надо срочно отправляться на планету Клиаанд в Системе Эпсилон Инди, которая была втянута в межзвездную войну. Джима и Ангелину отправляют в это вражеское, охваченное страхом общество, которым правит упрямый Край и его банда серых людей.

Итак, Джиму и Ангелине надо отправляться на планету Клиаанд, поэтому им надо вычислить оптимальный маршрут до Клиаанда . Для минимизации стоимости доставки Джим и Ангелина вылетают каждый с планеты, на которой находятся в данный момент, а затем могут встретиться на некоторой планете, где арендуют один космический корабль. Конечно, так они поступят только в том случае, если суммарный пройденный путь становится меньше. В противном случае каждый из них долетит до Клиаанда самостоятельно. Космическая служба перевозок выполняет перевозки только по утвержденным маршрутам от планеты к планете и оценивает аренду одного космического корабля на один такой сегмент в 1 миллион лигарелов.

Чтобы оптимизировать вариант доставки на Клиаанд , Джим должен вычислить количество сегментов на оптимальном совместном маршруте.

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

В первой строке входного файла содержится пять целых чисел N, M, K, P, C - количество планет, количество маршрутных сегментов, номера планет, где находятся Джим и Ангелина соответственно, номер планеты Клиаанд. Известно, что N ≤ 1000, Далее следует M строк, в каждой из которых задается описание маршрутного сегмента. Каждый такой сегмент задается номерами планет, которые он соединяет. Все маршруты с двусторонним движением.

К сожалению, может так случиться, что существующее расписание не сможет обеспечить доставку Джима и Ангелины на планету Клиаанд. В этом случае нашим героям придется обращаться за помощью к правительству Лиги, а Вы должны вывести слово Impossible.

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

В результирующий файл Вы должны вывести ответ на задачу.

Пример входного и выходного файлов

        input.txt               output.txt       
5 5 1  2 5 
1 3  
1 4 
2 4 
3 5 
4 5 
3          
5 4 1  2 5 
1 3  
1 4 
3 5 
4 5
Impossible