Задача №111826. Странный город
В одной стране есть странный город. В этом городе есть \(n\) перекрестков и \(m\) улиц. Каждая улица соединяет ровно два различных перекрестка и по каждой улице можно двигаться в обоих направлениях.
Однажды с целью борьбы с пробками мэр города решил провести дорожную реформу. Он решил запретить автомобильное движение на некоторых улицах и сделать их пешеходными. При этом исследования департамента транспорта показали, что результаты реформы будут оптимальными, если после ее осуществления из каждого перекрестка будет выходить нечетное число улиц, на которых разрешено автомобильное движение.
Подчиненные мэра озадачены. Они никак не могут исполнить приказ мэра. Вам предлагается сделать это за них. Вам задана карта города, требуется решить, какие улицы необходимо сделать пешеходными, а какие - оставить для автомобилей, чтобы в результате реформы из каждого перекрестка выходило нечетное число улиц, по которым разрешено движение автомобилей.
В первой строке заданы целые числа \(n\) и \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(0 \le m \le 2 \cdot 10^5\)) - количество перекрестков и количество дорог в городе соответственно.
В следующих \(m\) строках заданы дороги, каждая дорога описана в отдельной строке. В \((i+1)\)-й строке описывается дорога с номером \(i\). Каждая дорога задается двумя целыми числами \(v\) и \(u\) - номерами двух перекрестков, которые эта дорога соединяет (\(1 \le v, u \le n\)).
Гарантируется, что дорога не соединяет перекресток с самим собой.
Гарантируется, что любая пара перекрестков соединена не более чем одной дорогой.
Не гарантируется, что от исходно любого перекрестка можно добраться до любого другого по улицам.
Если удовлетворить условие в приказе мэра невозможно, выведите единственное число \(-1\) в первой строке выходного файла.
Иначе в первой строке выведите число \(k\) - количество дорог, которые нужно оставить для автомобильного движения. В следующей строке выведите \(k\) различных чисел через пробел - номера этих дорог. Дороги пронумерованы от 1 до \(m\) в том порядке, в котором они заданы во входном файле.
2 1 1 2
1 1
4 4 1 2 2 3 3 4 4 1
2 2 4