Новый остров
На недавно открытом острове была обнаружена команда архитекторов, которая усердно работала над планом дорог для соединения важных частей острова. Однако из-за ограниченного бюджета необходимо изменить проект, чтобы сделать его более доступным.
В предложенном плане каждая дорога имеет уникальный id от 1 до E (где E — количество дорог) и стоимость, равную 2^id. Таким образом, затраты выражены в различных степенях двойки. Мы стремимся исключить некоторые дороги из плана, чтобы минимизировать общую стоимость, при этом сохраняя все места соединенными. Однако нельзя исключать дороги произвольно. Ограничение состоит в том, что в новом плане расстояние между любыми двумя местами не должно превышать в два раза их расстояние в оригинальном плане. Расстояние между двумя местами определяется как минимальное количество дорог, соединяющих их. Оригинальный план дорог представлен в виде графа, и ваша задача — найти наиболее экономичный способ исключения дорог в соответствии с данным ограничением.
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается со строки, содержащей два целых числа N (1 ≤ N ≤ 200) и E, которые обозначают количество вершин (мест) и рёбер (дорог) соответственно. Далее следуют E строк, каждая из которых описывает дорогу. i-я строка содержит два числа v_i и u_i, указывающие, что дорога с id i соединяет места v_i и u_i. Ввод завершается строкой, содержащей два нуля.
Выходные данные
Для каждого теста выведите количество исключенных дорог, а затем в одной строке перечислите их идентификаторы в порядке возрастания.