Задача K. Змея в метро ≡

Условие

2390 год. В заброшенном метрополитене города N-ска завелась громадная змея-мутант. Она ползает вдоль перегонов между станциями, повергая в ужас случайно забредающих под землю потомков людей. Размеры змеи настолько велики, что иногда голова появляется на той станции, вдоль которой еще ползет какая-то другая часть тела, и змея повергает в ужас сама себя. Чтобы избавиться от этой проблемы, змея поймала вас и потребовала написать для нее программу, которая может ей прокладывать кратчайший маршрут для головы от одной станции до другой, не проползая при этом по станциям, где находятся участки ее тела.

Будем называть маршрутом последовательность станций, каждые две последовательные из которых соединены перегоном.

Все перегоны в метрополитене имеют одинаковую длину, а змея имеет длину в (l − 0.5) перегонов. Змея может ползти вдоль перегонов, переползая с одного на другой на станциях. Змея может ползти вдоль перегона только в один слой, а ее голова не может появляться на станции, если в этот момент по станции проползает другая часть ее тела. Змея умеет ползать только головой вперед.

С точки зрения теории графов метрополитен города N-ска является вершинным кактусом. Это означает, что ни одна станция не лежит на двух различных циклических маршрутах и никакие два перегона не соединяют одну и ту же пару станций, никакой перегон не соединяет станцию саму с собой, от каждой станции до любой другой до появления змеи можно было добраться по перегонам.

По заданным карте метрополитена, начальному положению змеи и станции, на которую змея хочет поместить свою голову, выясните, какое минимальное количество перегонов придется проползти змее.

Формат входного файла

В первой строке ввода записано два числа n и k — количество станций и количество перегонов в метрополитене (1 ≤ n, k ≤ 100 000). В следующих k строках записано по два различных целых числа a и b — номера станций, соединенных соответствующим перегоном.

В следующей строке записано единственное число l, характеризующее длину змеи. В следующей строке записано l + 1 число: номера станций, на которых лежат последовательные части змеи, начиная с головы, а также номер станции, в перегоне к которой лежит хвост змеи длиной в 0.5 перегона. Исходно змея расположена таким образом, что ни в каком перегоне не находится одновременно две различных части змеи и змея не пересекает себя ни на какой станции.

В последней строке записано единственное целое число — станция, на которую змея хочет поместить свою голову.

Формат выходного файла

Если змея сможет выполнить свою задачу, выведите длину пути — количество перегонов, через которые необходимо проследовать голове змеи.

Если задача невыполнима, выведите единственное число  − 1.

Примеры тестов

6 6
1 2
2 3
3 4
4 5
5 2
4 6
2
5 2 3
1

4