29039번 - Хэллоуин 스페셜 저지다국어

В этом году на Хэллоуин, как обычно, монстры будут пугать людей. В этом году граф Дракула взял на себя ответственность все спланировать. У каждого монстра он узнал, какие дома тот хочет <<навестить>>, соединил линиями на листке соответствуюещего монстра с соответствующими домами, а после этого оставил листок с записями на своем столе в кабинете и ушел по делам.

В его отсутвие Квазимодо зашел в кабинет и увидел на столе интересный листок какими-то линиями --- листок, оставленный Дракулой. Недолго думая, он нарисовал еще несколько линий на нем, а потом положил лист на место и ушел. Вернувшись, граф Дракула не мог не заметить изменения в листе. Кроме того, он осознал, что после добавлений Квазимодо теперь не ясно, где на листке отмечены дома, а где монстры. И следовательно, Хэллоуин на грани срыва.

Теперь Дракула просит вас попробовать вернуть лист с линиями в начальное состояние, то есть стереть с него несколько линий так, чтобы после этого все объекты на листике можно было разбить на две группы --- дома и монстры, чтобы линии проходили только между этими группами. Он не верит, что Квазимодо мог нарисовать очень много линий, поэтому он попросил вас удалить у каждого объекта не более половины исходящих из него линий. Помогите Дракуле привести лист к корректному состоянию или скажите, что его предположение неверно.

В первой строке входного файла содержится два числа $n$, $m$ ($1 \le n, m \le 2\,000$) --- количество объектов на листке и линий между ними соответственно.

В следующих $m$ строках содержится описание двусторонних линий, соединяющих объекты. В $i+1$-й строке входного файла содержится описание $i$-й линии. Описание состоит из двух чисел $u$, $v$ ($1 \le u, v \le n, u \ne v$) --- номера объектов, соединенных линией. Гарантируется, что между одной парой объектов проведено не более одной линии.

В первой строке выходного файла выведите количество удаленных линий.

Во второй строке выведите номера удаленных линий. Линии нумеруются с 1 в порядке следования во входном файле. После удаления количество исходящих линий у каждой вершины должно уменьшиться не более чем вдвое.