Кабельна телевізійна мережа
Взаємозв'язок реле в кабельній телевізійній мережі є двонаправленим. Мережа вважається з'єднаною, якщо існує принаймні один шлях між кожною парою реле в мережі. В іншому випадку мережа є роз'єднаною. Порожня мережа або мережа з одним реле вважається з'єднаною. Фактор безпеки 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), які не містять пробілів, пробіли можуть вільно з'являтися у вводі. Вхідні дані завершуються кінцем файлу і є коректними.
Вихідні дані
Для кожного набору даних програма виводить на стандартний вихід, з початку рядка, фактор безпеки закодованої мережі.