eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Удаление рёбер

Удаление рёбер

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Дано неорієнтований граф без петель та кратних ребер. Знайти мінімальну кількість ребер, яку слід видалити, щоб граф став незв'язним.

Вхідні дані

Два числа n та k (2n100, 0kn·(n-1)/2) - кількість вершин та ребер у графі. Далі йдуть k рядків по два числа в кожному - a, b (1a, bn) - номери вершин, сполучених ребром.

Вихідні дані

Одне число - мінімальна кількість ребер, яку необхідно видалити щоб граф став незв'язним.

Приклад

Вхідні дані #1
3 3
1 2
2 3
3 1
Вихідні дані #1
2
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь