Задача №1552. Пробки
C недавних пор в городе N стали регулярно случаться пробки. Для отслеживания дорожной обстановки Городничий повелел установить видеокамеры таким образом, чтобы каждая улица была видна хотя бы с одной видеокамеры. Дорожная сеть города N устроена таким образом: каждая улица является абсолютно прямой (то есть для того, чтобы следить за обстановкой на этой улице достаточно одной видеокамеры в любой ее точке), каждая улица соединяет две какие-то площади (для простоты разработки проекта видеонаблюдения площади пронумерованы числами от 1 до \(P\), \(P\) – натуральное, не превосходит 15).
Как и всякому градоначальнику, Городничему хотелось бы уменьшить количество устанавливаемых видеокамер, в целях экономии городского бюджета. Следует заметить, что в городе решено использовать камеры с круговым обзором (то есть если камера установлена на какой-то площади, то она контролирует все примыкающие к этой площади улицы).
Напишите программу, которая определит минимальное количество камер, необходимых для контроля за улицами города \(N\).
сначала вводится число \(P\) – общее количество площадей, затем число \(S\) – количество улиц в городе. Затем следует \(S\) (натуральное) строк по два числа в каждой – описание улиц. Улица описывается двумя числами – номерами площадей, которые она соединяет. Гарантируется, что двигаясь по улицам города можно попасть с любой его площади на любую другую.
выведите единственное число – минимальное количество видеокамер, которое потребуется для отслеживания дорожной обстановки
2 1 1 2
1
4 5 1 2 1 3 1 4 2 3 2 4
2