Надійні мережі#2622
Ви відповідаєте за проєктування університетської мережі між будівлями й дуже стурбовані її надійністю та вартістю. Тому ви вирішили додати певну надмірність у мережу, водночас прагнучи зберегти її якомога дешевшою. Зокрема, ви хочете побудувати найдешевшу мережу, таку що, якщо будь-яка одна лінія вийде з ладу, всі будівлі все одно можуть спілкуватися між собою. Така мережа називатиметься мінімально надійною мережею.
Є кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа (n \leq 15) і (m \leq 20) — кількість будівель (пронумерованих від до ) та кількість можливих з'єднань між будівлями. Кожен із наступних рядків містить b_1 b_2 (усі додатні цілі числа), що означає вартість для з'єднання будівель b_1 та b_2. Усі з'єднання двосторонні.
Останній тестовий випадок містить n = m = 0 й не опрацьовується.
Для кожного тестового випадку виведіть один рядок із вартістю мінімальної надійної мережі. Якщо така мережа існує, відповідь має бути у вигляді:
The minimal cost for test case is .
де — номер тестового випадку (починаючи з ), а — вартість. Якщо побудувати надійну мережу неможливо, виведіть рядок такого вигляду:
There is no reliable net possible for test case .
Приклад 1