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

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

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклад

Вхідні дані #1
5 1 4
1 2
2 3
1 3
4 5
Вихідні дані #1
1