e-olymp
Задачи

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

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

Все вы помните задачу "Слово спонсора" с новогодних соревнований. Напомню кратко проблему, стоявшую в этой задаче: после завершения соревнований спонсор пожелал разослать победителям призы.

Но почтовая система не совершенна и не всем участникам призы могли быть доставлены. Конкретнее, в стране есть n почтовых отделений, пронумерованных от 1 до n. Спонсор отправляет призы с отделения под номером s. Также нам известны пары отделений, имеющих связь между собой, то есть, между какими отделениями может передаваться почта.

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

prb37

Входные данные

В первой строке заданы три числа - количество отделений 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