e-olymp
Задачі

Пошта спонсора

Пошта спонсора

prb37 Усі ви пам'ятаєте задачу "Слово спонсора" з новорічного змагання. Нагадаю коротко проблему, яка постала в цій задачі: після завершення змагання спонсор захотів розіслати переможцям призи.

Але поштова система не досконала і не до всіх учасників призи могли бути доставлені. Конкретніше, у країні є n поштових відділень пронумерованих від 1 до n. Спонсор відправляє призи з відділення з номером s. Також ми знаємо пари відділень, які мають зв'язок між собою, тобто, між якими відділеннями може передаватися пошта.

Перед новим змаганням спонсор вирішив наперед перестрахуватися і забезпечити можливість доставки призів. Для цього спонсор готовий за свої кошти встановити кілька нових зв'язків між деякими парами поштових відділень. Ваша задача - порахувати, яку найменшу кількість нових зв'язків повинен забезпечити спонсор, щоб призи можна було доставити після змагання всім учасникам, не зважаючи на те, де вони проживають і яким з поштових відділень користуються.

Вхідні дані

В першому рядку задано три числа - кількість відділень n (1n100000), номер відділення, яким користується спонcор s (1sn) та кількість існуючих зв'язків між парами відділень k (0k100000).

В наступних k рядках записано по 2 числа a та b - номери відділень, між якими здійснюється перевезення пошти (a та b - різні числа з інтервалу [1; n]). Усі пари (a,b) різні.

Вихідні дані

Єдине число - найменша можлива кількість нових зв'язків, які необхідно додати, щоб пошту можна було доставити з відділення s у будь-яке інше відділення.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 1 4
1 2
2 3
1 3
4 5
Вихідні дані #1
1