eolymp
bolt
Try our new interface for solving problems
Problems

Штрафы

Штрафы

Time limit 0.5 seconds
Memory limit 128 MiB

Степан недавно приобрёл автомобиль, но водительские права ещё не получил. В связи с этим он не имеет права на нём ездить. Но его жена уже спланировала выходные, и поездка в столицу входит в эти планы. Недолго думая, Степан нашёл выход. Известно, что посты ГАИ стоят не на всех дорогах, а только на тех, которые объехать нельзя, потому что так они поймают больше правонарушителей. Известно, что в стране Степана N городов, и они соединены M дорогами. Понятно, никакие две дороги не соединяют одну и ту же пару городов (в стране ведь умные люди работают). Степан живёт в городе А, а столица находится в городе 1. При отсутствии водительских прав штраф составляет 1000 рублей.

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

Input data

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

Output data

Выведите в одной строке единственное число – количество рублей, которые Степан должен иметь при себе. Если добраться нельзя, то вывести -1.

Examples

Input example #1
6 7
1 2 
2 3
3 1
3 4
4 5
4 6
5 6
6
Output example #1
1000
Source Stage III All-Ukrainian School Olympiad 2012-2013, Round 2