eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Штрафи

Штрафи

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 128 MiB

Степан нещодавно купив автомобіль, але водійські права ще не отримав. В зв’язку з цим він не має права на ньому їздити. Але його дружина вже спланувала вихідні, і поїздка до столиці входить в ці плани. Недовго думаючи, Степан знайшов вихід. Відомо, що пости ДАІ стоять не на усіх дорогах, а лише на тих, які обминути не можна, тому що так вони спіймають більше правопорушників. Відомо, що в країні Степана N міст, і вони з’єднані M дорогами. Зрозуміло, ніякі дві дороги не з’єднують одну й ту саму пару міст (в країні ж розумні люди працюють). Степан живе в місті А, а столиця знаходиться в місті 1. За відсутність водійських прав штраф складає 1000 гривень.

Скажіть, скільки в нього має бути при собі грошей, щоб він міг виплатити всі штрафи.

Вхідні дані

Перший рядок містить два числа N, M (2N10^5, 1M10^5). Інші М рядків містять два числа X_i та Y_i, які описують дорогу між містом X_i та містом Y_i. В останньому рядку записано число A (2AN) – місто в якому живе Степан.

Вихідні дані

Виведіть в одному рядку єдине число – кількість гривень, які Степан має мати при собі. Якщо добратися не можна, то вивести -1.

Приклад

Вхідні дані #1
6 7
1 2 
2 3
3 1
3 4
4 5
4 6
5 6
6
Вихідні дані #1
1000
Джерело III етап Всеукраїнської олімпіади школярів 2012-2013, 2 тур