Оцінка Безпеки#2561

Оцінка Безпеки

1 секунда

64 мегабайти

Середня

Вузли кабельної мережі між собою з'єднані кабелями так, що кожен кабель з'єднує одну пару різних вузлів, а пара вузлів може бути з'єднана кількома кабелями. Мережа вважається зв'язною, якщо будь-які два вузли з'єднані безпосередньо або опосередковано; інакше, мережа є незв'язною. Рівень безпеки $S$ мережі визначається так:

$S$ дорівнює $0$ , якщо мережа незв'язна, або якщо кількість вузлів $0$ чи $1$ .
Якщо кількість вузлів більша за $1$ , тоді $S$ — це мінімальна кількість кабелів, видалення яких роз'єднує мережу. Тобто, при видаленні будь-яких $S - 1$ S-1 кабелів мережа залишається зв'язною, але існують $S$ кабелів, видалення яких роз'єднує мережу.

Наприклад, розглянемо мережу на рисунку $1$ , де вузли відповідають заштрихованим колам, а кабелі показані лініями. Мережа залишається зв'язною при видаленні будь-якого одного кабелю, але видалення кабелів $(0, 2)$ та $(1, 3)$ роз'єднує мережу. Інший спосіб роз'єднати мережу — видалити кабелі $(2, 4)$ та $(2, 4)$ . Рівень безпеки $S = 2$ S = 2.

Напишіть програму, яка зчитує кілька наборів даних з текстового файлу і обчислює рівень безпеки кабельних мереж, закодованих у цих наборах даних.

Вхідні дані

Кожен набір даних починається з двох цілих чисел: кількість вузлів $0 \leq n \leq 100$ 0 \le n \le 100 і кількість кабелів $0 \leq m \leq 1000$ 0 \le m \le 1000 у мережі. Далі йдуть $m$ пар $(u, v)$ , де $u < v$ u < v і $u$ та $v$ — ідентифікатори вузлів (цілі числа від $0$ до $n - 1$ n-1). Пара $(u, v)$ позначає кабель, що з'єднує вузли $u$ та $v$ . Пари можуть бути в довільному порядку. Окрім пар $(u, v)$ , які не містять пробілів, пробіли у введенні можуть з'являтися довільно. Вхідні дані завершуються кінцем файлу і є коректними.

Вихідні дані

Для кожного набору даних програма повинна вивести, з початку рядка, рівень безпеки закодованої мережі у стандартний потік виводу.

Приклади

Приклад 1