Кабельное телевидение
Взаимосвязь реле в кабельной сети телевидения является двунаправленной. Сеть считается связанной, если между каждой парой реле в сети существует хотя бы один путь. В противном случае сеть считается разъединенной. Пустая сеть или сеть с одним реле также считается связанной. Коэффициент безопасности f сети с n реле определяется следующим образом:
n, если сеть остается связанной независимо от количества удаленных реле.
Минимальное количество реле, удаление которых разъединяет сеть.
Рисунок 1. Кабельная сеть телевидения
Например, рассмотрим сети на рисунке 1, где круги обозначают реле, а сплошные линии — кабели связи. Сеть (a) остается связанной независимо от количества удаленных реле, и, согласно правилу (1), f=n=3. Сеть (b) разъединяется, когда 0 реле удалены, следовательно, f=0 по правилу (2). Сеть (c) разъединяется, когда удалены реле 1 и 2 или 1 и 3. Коэффициент безопасности равен 2.
Входные данные
Напишите программу, которая считывает несколько наборов данных из стандартного ввода и вычисляет коэффициент безопасности для кабельных сетей, закодированных этими наборами данных. Каждый набор данных начинается с двух целых чисел: 0 ≤ n ≤ 50, количество реле в сети, и m, количество кабелей в сети. Далее следуют m пар данных (u, v), u < v, где u и v — идентификаторы реле (целые числа в диапазоне 0..n-1). Пара (u, v) обозначает кабель, соединяющий реле u и v. Пары могут встречаться в любом порядке. За исключением пар (u, v), которые не содержат пробелов, пробелы могут свободно встречаться во входных данных. Входные данные заканчиваются концом файла и являются корректными.
Выходные данные
Для каждого набора данных программа выводит на стандартный вывод, начиная с новой строки, коэффициент безопасности закодированной сети.