Эффективное перепроектирование (НТО 25/26 :: ИЭС)

Условие

В рамках модернизации районной сети подстанции заменены на реклоузеры, способные направлять энергию по любому ребру в любом направлении. Компания «Никола Электроник» гарантирует 100%-ную* надёжность реклоузеров, они никогда не ломаются.

В вашем распоряжении связная сеть с главной подстанцией и реклоузерами. В ней слишком много лишних ЛЭП (линий электропередачи), которые невыгодно содержать. Нужно удалить как можно больше ЛЭП так, чтобы сеть оставалась связной, и чтобы все реклоузеры в среднем передавали мощность с главной подстанции как можно большему числу других реклоузеров в сети (это целевой показатель, а мы – за эффективность!).

Формат входных данных

В первой строке два целых числа через пробел, N (количество узлов) и M (количество ЛЭП).

Далее M строк, в каждой два целых числа – соединяемые узлы (нумерация с 0, ЛЭП неориентированная). Главная подстанция имеет номер 0.

Формат выходных данных

В первой строке одно целое число K – количество удалённых ЛЭП.

Во второй строке K целых чисел – номера удалённых ЛЭП.

Для решения этой задачи у вашей команды есть 20 попыток.

* Проверялось в солнечную безветренную погоду. Не является офертой.

Видео-разбор