Лехе надоело играть с полным графом, который ему подарили в прошлый раз. Теперь он проходит компьютерную игру, где на каждом уровне ему сначала выдается связный неориентированный граф из n вершин и m ребер. Граф может содержать кратные ребра, но не содержит петель. Далее для каждой вершины задается число di, которое может равняться 0, 1 или - 1. Чтобы пройти уровень, нужно найти любое «хорошее» подмножество ребер графа или сообщить, что его не существует. Подмножество называется «хорошим», если оставив в исходном графе только ребра из него, то для каждой вершины i будет верно, что di = - 1 или ее степень по модулю 2 равна di. Леха хотел бы поскорее пройти игру до конца и похвастаться своим друзьям, поэтому он просит Вашей помощи.
Выходные данные
Выведите - 1 в единственной строке, если решения не существует. Иначе в первой строке выведите целое число k — количество рёбер в ответе. В следующих k строках номера ребер в подмножестве. Ребра нумеруются в порядке ввода, начиная с 1.
Примечание
В первом примере у нас есть одна вершина без рёбер. Её степень 0 и получить 1 не получится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0
1
|
-1
|
|
2
|
4 5
0 0 0 -1
1 2
2 3
3 4
1 4
2 4
|
0
|
|
3
|
2 1
1 1
1 2
|
1
1
|
|
4
|
3 3
0 -1 1
1 2
2 3
1 3
|
1
2
|