{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"eo-paper__content\"\u003e\u003ch1 class\u003d\"eo-paper__header\"\u003eПочта спонсора\u003c/h1\u003e\u003cdiv class\u003d\"markdown\"\u003e\u003cp\u003eВсе вы помните задачу \"Слово спонсора\" с новогодних соревнований. Напомню кратко проблему, стоявшую в этой задаче: после завершения соревнований спонсор пожелал разослать победителям призы.\u003c/p\u003e\u003cp\u003eНо почтовая система не совершенна и не всем участникам призы могли быть доставлены. Конкретнее, в стране есть \u003cstrong\u003en\u003c/strong\u003e почтовых отделений, пронумерованных от \u003cstrong\u003e1\u003c/strong\u003e до \u003cstrong\u003en\u003c/strong\u003e. Спонсор отправляет призы с отделения под номером \u003cstrong\u003es\u003c/strong\u003e. Также нам известны пары отделений, имеющих связь между собой, то есть, между какими отделениями может передаваться почта.\u003c/p\u003e\u003cp\u003eПеред новыми соревнованиями спонсор решил наперед перестраховаться и гарантировать возможность доставки призов. Для этого спонсор готов за свои средства установить несколько новых связей между некоторыми парами почтовых отделений. Ваша задача - посчитать, какое наименьшее количество новых связей должен создать спонсор, чтобы призы можно было доставить после соревнований всем участникам, не смотря на то, где они проживают и каким почтовым отделением пользуются.\u003c/p\u003e\u003cp\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/55c58d94749b0369a07acb274740cae9?v\u003d1562441118\" alt\u003d\"prb37\"\u003e\u003c/p\u003e\u003ch4\u003eВходные данные\u003c/h4\u003e\u003cp\u003eВ первой строке заданы три числа - количество отделений \u003cstrong\u003en\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003en\u003c/strong\u003e ≤ \u003cstrong\u003e100000\u003c/strong\u003e), номер отделения, которым пользуется спонcор \u003cstrong\u003es\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003es\u003c/strong\u003e ≤ \u003cstrong\u003en\u003c/strong\u003e) и количество существующих связей между парами отделений \u003cstrong\u003ek\u003c/strong\u003e (\u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003ek\u003c/strong\u003e ≤ \u003cstrong\u003e100000\u003c/strong\u003e).\u003c/p\u003e\u003cp\u003eВ следующих \u003cstrong\u003ek\u003c/strong\u003e строках записано по \u003cstrong\u003e2\u003c/strong\u003e числа \u003cstrong\u003ea\u003c/strong\u003e и \u003cstrong\u003eb\u003c/strong\u003e - номера отделений, между которыми осуществляется перевозка почты (\u003cstrong\u003ea\u003c/strong\u003e и \u003cstrong\u003eb\u003c/strong\u003e - разные числа с интервала [\u003cstrong\u003e1\u003c/strong\u003e; \u003cstrong\u003en\u003c/strong\u003e]). Все пары (\u003cstrong\u003ea\u003c/strong\u003e, \u003cstrong\u003eb\u003c/strong\u003e) разные.\u003c/p\u003e\u003ch4\u003eВыходные данные\u003c/h4\u003e\u003cp\u003eВывести наименьшее возможное количество новых связей, которые необходимо создать, чтобы почту можно было доставить с отделения \u003cstrong\u003es\u003c/strong\u003e в любое другое отделение.\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003cdiv class\u003d\"mdl-grid mdl-grid--no-spacing\"\u003e\n \u003cdiv class\u003d\"mdl-cell mdl-cell--6-col\"\u003e\n \u003cdiv class\u003d\"eo-label\"\u003e\n Input example #1\n \u003c/div\u003e\n \u003cpre class\u003d\"eo-code\"\u003e5 1 4\n1 2\n2 3\n1 3\n4 5\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"mdl-cell mdl-cell--6-col\"\u003e\n \u003cdiv class\u003d\"eo-label\"\u003e\n Output example #1\n \u003c/div\u003e\n \u003cpre class\u003d\"eo-code\"\u003e1\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}