eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дивне місто

Дивне місто

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

В одній країні є дивне місто. У цьому місті є n перехресть та m вулиць. Кожна вулиця з'єднує рівно два різних перехрестя і по кожній вулиці можна рухатись в обох напрямках.

Одного разу з метою боротьби з пробками мер міста вирішив провести дорожну реформу. Він вирішив заборонити автомобільний рух на деяких вулицях і зробити їх пішоходними. При цьому дослідження департаменту транспорту показали, що результати реформи будуть оптимальними, якщо після її здійснення з кожного перехрестя буде виходити непарне число вулиць, на яких дозволено автомобільний рух.

Підлеглі мера занепокоєні. Вони ніяк не можуть виконати наказ мера. Вам пропонується зробити це за них. Вам задано карту міста, потрібно вирішити, які вулиці необхідно зробити пішоходними, а які — залишити для автомобілів, щоб в результаті реформи з кожного перехрестя виходило непарне число вулиць, по яким дозволено рух автомобілів.

Вхідні дані

У першому рядку задано цілі числа n та m (1n2·10^5, 0m2·10^5) — кількість перехресть та кількість доріг у місті відповідно.

У наступних m рядках задано дороги, кожну дорогу описано у окремому рядку. У (i+1)-му рядку описано дорогу з номером i. Кожна дорога задається двома цілими числами v та u — номерами двох перехресть, які ця дорога з'єднує (1v, un).

Гарантується, що дорога не з'єднує перехрестя з самим собою.

Гарантиується, що довільна пара перехресть з'єднана не більше ніж однією дорогою.

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

Вихідні дані

Якщо задовольнити умову у наказі мера не можливо, виведіть єдине число -1 у першому рядку вихідного файлу.

Інакше у першому рядку виведіть число k — кількість доріг, які потрібно залигити для автомобільного руху. У наступному рядку виведіть k різних чисел через пропуск — номери цих доріг. Дороги пронумеровані від 1 до m у тому порядку, у якому вони задані у вхідному файлі.

Приклад

Вхідні дані #1
2 1
1 2
Вихідні дані #1
1
1
Джерело XIII Всеросійська командна олімпіада школярів з програмування