F. Почти двудольный граф
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ рёбер. В графе отсутствуют петли и кратные рёбра. Не гарантируется, что данный граф — связный.

Напомним, что граф называется двудольным, если можно покрасить все вершины в два цвета так, чтобы ни одно ребро не соединяло две вершины одного цвета.

Ваша задача — определить, можно ли удалить не более $$$k$$$ рёбер таким образом, чтобы получившийся граф стал двудольным.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 1\,000$$$; $$$1 \le m \le 1\,000$$$; $$$1 \le k \le 10$$$) — количество вершин и рёбер в графе, и максимальное число рёбер, которое можно удалить.

Далее следуют $$$m$$$ строк, $$$i$$$-я из них содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), означающих ребро между вершинами $$$x_i$$$ и $$$y_i$$$. В заданном графе отсутствуют петли и кратные рёбра.

Выходные данные

В первой строке выведите количество рёбер (не более $$$k$$$), которые необходимо удалить, чтобы граф стал двудольным. Во второй строке выведите $$$k$$$ различных чисел — номера рёбер для удаления.

Если такого набора рёбер размера не более $$$k$$$ не существует, в единственной строке выведите -1.

Если существует несколько подходящих наборов рёбер, то выведите любой из них. Номера рёбер можно выводить в произвольном порядке. Рёбра пронумерованы целыми числами от $$$1$$$ до $$$m$$$ в порядке их следования во входных данных.

Примеры
Входные данные
4 5 1
1 2
1 3
2 3
2 4
3 4
Выходные данные
1
3 
Входные данные
4 6 1
1 2
2 3
4 2
3 4
3 1
1 4
Выходные данные
-1
Входные данные
5 3 2
1 2
2 3
4 5
Выходные данные
0
Входные данные
5 6 10
1 2
3 2
5 3
3 4
4 5
1 4
Выходные данные
6
1 2 3 4 5 6