Новий острів
Новий острів було відкрито. Команда архітекторів наполегливо працювала і запропонувала план доріг для з'єднання важливих частин цього нового острова. Через брак коштів ми повинні змінити дизайн, щоб отримати доступний варіант.
У запропонованому плані кожна дорога має унікальний id від 1 до E (кількість доріг) і вартість, яка дорівнює 2^id. Отже, витрати є різними ступенями двійки. Ми хочемо вилучити деякі дороги з плану, щоб отримати мінімальну загальну вартість, при цьому всі місця залишаються з'єднаними. Але ми не можемо вилучати дороги без обмежень. У новому плані доріг відстань між будь-якими двома місцями не повинна перевищувати подвоєну відстань в оригінальному плані. Відстань між двома місцями визначається як мінімальна кількість доріг, що їх з'єднують. Оригінальний план доріг подано у вигляді графа, і вам потрібно знайти найбільш економічне вилучення доріг відповідно до обмеження.
Вхідні дані
У вхідних даних кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа N (1 ≤ N ≤ 200) та E, кількість вершин (місць) та ребер (доріг) відповідно. Специфікація доріг подається на наступних E рядках. i-й рядок містить два числа v_i та u_i, що означає, що дорога з id i знаходиться між місцями v_i та u_i. Вхід завершується рядком, що містить два нульових числа.
Вихідні дані
Для кожного тестового випадку виведіть кількість вилучених доріг, а потім зростаючий список їх id в одному рядку.