E. Большая чистка
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Дед Мороз со Снегурочкой после того, как раздали все подарки и исполнили все желания, вернулись в свою резиденцию и обнаружили, что она вся занесена снегом. Герои очень устали, и решили расчистить лишь дорожки между домиками. В резиденции n домиков, соединенных m дорожками. По дорожкам можно ходить в обоих направлениях.

Снегурочка предложила разделить работу: Дед Мороз будет чистить широкие дорожки, а она будет протаптывать узенькие. Для каждой дорожки герои определили, кто ее может чистить: либо Дед Мороз, либо Снегурочка. Для экономии усилий было решено расчистить дорожки так, чтобы выполнялись оба условия:

  • между любыми двумя домиками должен существовать ровно один простой путь по расчищенным дорожкам;
  • Дед Мороз должен расчистить столько же дорожек, сколько и Снегурочка.

И тут герои задумались: какие же дорожки им надо расчистить?

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

В первой строке входных данных записаны два целых положительных числа n и m (1 ≤ n ≤ 103, 1 ≤ m ≤ 105) — количество домиков и количество дорожек. Далее следует m строк, в каждой из которых задано описание одной дорожки: номера домиков, которые она соединяет, — x и y (1 ≤ x, y ≤ n), и кто ее собирается чистить («S» — Снегурочка, или «M» — Дед Мороз). По каждой дорожке можно ходить в обоих направлениях. Обратите внимание, что между двумя домиками может быть больше одной дорожки, и дорожка может вести из домика в него же.

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

Выведите «-1» без кавычек, если невозможно выбрать дорожки, которые будут расчищены по заданным правилам. В противном случае выведите в первую строку количество расчищенных дорожек, а во вторую — номера этих дорожек (дорожки нумеруются с 1 в том порядке, в котором они заданы во входных данных). Номера дорожек разрешается выводить в любом порядке. Каждый номер следует вывести ровно один раз. Числа при выводе разделяйте пробелами.

Примеры
Входные данные
1 2
1 1 S
1 1 M
Выходные данные
0

Входные данные
3 3
1 2 S
1 3 M
2 3 S
Выходные данные
2
2 1
Входные данные
5 6
1 1 S
1 2 M
1 3 S
1 4 M
1 5 M
2 2 S
Выходные данные
-1
Примечание

Путь называется простым, если все домики на пути попарно различны.