Новий острів#6910

Новий острів

1 секунда

64 мегабайти

Дуже легка

Новий острів було відкрито. Команда архітекторів наполегливо працювала і запропонувала план доріг для з'єднання важливих частин цього нового острова. Через брак коштів ми повинні змінити дизайн, щоб отримати доступний варіант.

У запропонованому плані кожна дорога має унікальний $i d$ від $1$ до $E$ (кількість доріг) і вартість, яка дорівнює $2^{i d}$ 2^{id}. Отже, витрати є різними ступенями двійки. Ми хочемо вилучити деякі дороги з плану, щоб отримати мінімальну загальну вартість, при цьому всі місця залишаються з'єднаними. Але ми не можемо вилучати дороги без обмежень. У новому плані доріг відстань між будь-якими двома місцями не повинна перевищувати подвоєну відстань в оригінальному плані. Відстань між двома місцями визначається як мінімальна кількість доріг, що їх з'єднують. Оригінальний план доріг подано у вигляді графа, і вам потрібно знайти найбільш економічне вилучення доріг відповідно до обмеження.

Вхідні дані

У вхідних даних кілька тестових випадків. Кожен тестовий випадок починається з рядка, що містить два цілі числа $N$ ( $1 \leq N \leq 200$ 1 \le N \le 200) та $E$ , кількість вершин (місць) та ребер (доріг) відповідно. Специфікація доріг подається на наступних $E$ рядках. $i$ -й рядок містить два числа $v_{i}$ v_i та $u_{i}$ u_i, що означає, що дорога з $i d$ $i$ знаходиться між місцями $v_{i}$ v_i та $u_{i}$ u_i. Вхід завершується рядком, що містить два нульових числа.

Вихідні дані

Для кожного тестового випадку виведіть кількість вилучених доріг, а потім зростаючий список їх $i d$ в одному рядку.

Приклади

Приклад 1