Штрафы
Степан недавно приобрёл автомобиль, но водительские права ещё не получил. В связи с этим он не имеет права на нём ездить. Но его жена уже спланировала выходные, и поездка в столицу входит в эти планы. Недолго думая, Степан нашёл выход. Известно, что посты ГАИ стоят не на всех дорогах, а только на тех, которые объехать нельзя, потому что так они поймают больше правонарушителей. Известно, что в стране Степана N городов, и они соединены M дорогами. Понятно, никакие две дороги не соединяют одну и ту же пару городов (в стране ведь умные люди работают). Степан живёт в городе А, а столица находится в городе 1. При отсутствии водительских прав штраф составляет 1000 рублей.
Скажите, сколько у него должно быть при себе денег, чтобы он смог выплатить все штрафы.
Входные данные
Первая строка содержит два числа N, M (2 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5). Остальные М строк содержат по два числа X_i и Y_i, которые описывают дорогу между городом X_i и городом Y_i. В последней строке записано число A (2 ≤ A ≤ N) – город в котором живёт Степан.
Выходные данные
Выведите в одной строке единственное число – количество рублей, которые Степан должен иметь при себе. Если добраться нельзя, то вывести -1.