Дан неориентированный граф, состоящий из $$$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 11 21 32 32 43 4
1 3
4 6 11 22 34 23 43 11 4
-1
5 3 21 22 34 5
0
5 6 101 23 25 33 44 51 4
6 1 2 3 4 5 6
| Название |
|---|


