Zart PMP вышел в финал мирового чемпионата ICPC World Finals, который проводится в китайском городе Харбине. Сходив на групповую экскурсию в Sun Island Park и насладившись выставкой снежных скульптур, PMP должен вернуться к автобусам до того, как они уедут. Но парк очень большой, и он не знает, как найти стоянку.
В парке есть n перекрестков, пронумерованных от 1 до n. Есть m двунаправленных дорог, соединяющих некоторые пары из этих перекрестков. На k перекрестках волонтеры ICPC помогают командам и показывают им путь к месту назначения. Волонтеры стоят в фиксированных точках и не двигаются, никакие два волонтера не стоят на одном перекрестке.
Когда PMP просит волонтера указать путь до стоянки, тот/та может описать ему весь путь. Но парк полностью покрыт льдом и снегом и все выглядит почти одинаково. Из-за этого PMP может запомнить не более q перекрестков после каждого вопроса (не считая перекрестка, на котором он стоит в данный момент). Он всегда рассказывает волонтерам о своей слабой памяти и если нет прямого пути длиной не более q (в количестве дорог), ведущему к стоянке, то волонтер направит PMP к другому волонтеру (расстояние до которого в количестве дорог, разумеется, не должно превышать q). Волонтеры ICPC прекрасно знают парк и всегда указывают PMP самый лучший путь. Таким образом, если существует путь до стоянки, PMP безусловно найдет его.
Изначально PMP находится на перекрестке s, а автобусы стоят на перекрестке t. На перекрестке s всегда есть волонтер. Ваша задача — найти, при каком минимальном значении q PMP сможет найти автобусы.
Выходные данные
Выведите на единственной строке ответ к задаче: минимальное значении q, при котором PMP сможет найти автобусы. Если PMP не сможет найти автобусы ни при каком значении q выведите -1.
Примечание
Первый пример проиллюстрирован ниже. Синим отмечены перекрестки, в которых находятся волонтеры. Пунктирная линия показывает возможный путь, для такого пути ответ q = 3:
Во втором примере, при q = 3 PMP может дойти до перекрестка номер 6, а потом дойти до автобусной остановки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 6 3
1 3 6
1 2
2 3
4 2
5 6
4 5
3 4
1 6
|
3
|
|
2
|
6 5 3
1 5 6
1 2
2 3
3 4
4 5
6 3
1 5
|
3
|