Дед Мороз со Снегурочкой после того, как раздали все подарки и исполнили все желания, вернулись в свою резиденцию и обнаружили, что она вся занесена снегом. Герои очень устали, и решили расчистить лишь дорожки между домиками. В резиденции n домиков, соединенных m дорожками. По дорожкам можно ходить в обоих направлениях.
Снегурочка предложила разделить работу: Дед Мороз будет чистить широкие дорожки, а она будет протаптывать узенькие. Для каждой дорожки герои определили, кто ее может чистить: либо Дед Мороз, либо Снегурочка. Для экономии усилий было решено расчистить дорожки так, чтобы выполнялись оба условия:
- между любыми двумя домиками должен существовать ровно один простой путь по расчищенным дорожкам;
- Дед Мороз должен расчистить столько же дорожек, сколько и Снегурочка.
И тут герои задумались: какие же дорожки им надо расчистить?
Выходные данные
Выведите «-1» без кавычек, если невозможно выбрать дорожки, которые будут расчищены по заданным правилам. В противном случае выведите в первую строку количество расчищенных дорожек, а во вторую — номера этих дорожек (дорожки нумеруются с 1 в том порядке, в котором они заданы во входных данных). Номера дорожек разрешается выводить в любом порядке. Каждый номер следует вывести ровно один раз. Числа при выводе разделяйте пробелами.
Примечание
Путь называется простым, если все домики на пути попарно различны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
1 1 S
1 1 M
|
0
|
|
2
|
3 3
1 2 S
1 3 M
2 3 S
|
2
2 1
|
|
3
|
5 6
1 1 S
1 2 M
1 3 S
1 4 M
1 5 M
2 2 S
|
-1
|