Задачи
Почта спонсора
Почта спонсора
Все вы помните задачу "Слово спонсора" с новогодних соревнований. Напомню кратко проблему, стоявшую в этой задаче: после завершения соревнований спонсор пожелал разослать победителям призы.
Но почтовая система не совершенна и не всем участникам призы могли быть доставлены. Конкретнее, в стране есть $n$ почтовых отделений, пронумерованных от $1$ до $n$. Спонсор отправляет призы с отделения под номером $s$. Также нам известны пары отделений, имеющих связь между собой, то есть, между какими отделениями может передаваться почта.
Перед новыми соревнованиями спонсор решил наперед перестраховаться и гарантировать возможность доставки призов. Для этого спонсор готов за свои средства установить несколько новых связей между некоторыми парами почтовых отделений. Ваша задача --- посчитать, какое наименьшее количество новых связей должен создать спонсор, чтобы призы можно было доставить после соревнований всем участникам, несмотря на то, где они проживают и каким почтовым отделением пользуются.
\includegraphics{https://static.e-olymp.com/content/57/57d048339a9df77fb3a248e8c930268acf8c7407.gif}
\InputFile
В первой строке заданы три числа --- количество отделений $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)$ различны.
\OutputFile
Выведите наименьшее возможное количество новых связей, которые необходимо создать, чтобы почту можно было доставить с отделения $s$ в любое другое отделение.
Входные данные #1
5 1 4 1 2 2 3 1 3 4 5
Выходные данные #1
1