圣诞老人和他的助手精灵送完所有的礼物并实现了所有的愿望后,他们回到了北极,却发现北极已经被白雪覆盖了。两人都累了,决定只清除连接小屋的道路上的积雪。北极有n间小屋,与m条道路相连。人们可以沿着道路双向行驶。
精灵提出分道扬镳:圣诞老人将清理宽阔的道路,精灵将踏出狭窄的道路。对于每条路,他们决定由谁来清理:圣诞老人或精灵。为了尽量减少工作量,他们决定清理道路以满足这两个条件:
- 任何两个小屋之间都应该存在一条沿着已清理道路的简单路径;
- 圣诞老人和精灵应该清理相同数量的道路。
此时圣诞老人和他的助手小精灵想知道他们应该清理哪些道路?
输入
第一输入行包含两个正整数 n 和 m (1 ≤ n ≤ 103, 1 ≤ m ≤ 105) — 小屋数量和道路数量。然后是m行,每行都包含一条道路描述:它所连接的小屋数量——x和y(1≤x,y≤n)以及负责清理这条道路的人(“S”——代表精灵,“M”代表圣诞老人)。每条道路都可以双向行驶。请注意,两个小屋之间可以有多条道路,并且道路可以在同一个小屋内开始和结束。
输出
如果无法选择给定规则将清除的道路,则打印“-1”(不带引号)。否则,在第一行中打印应清除多少条道路,并在第二行中打印这些道路的编号(道路按照输入中出现的顺序从 1 开始编号)。允许以任意顺序打印道路编号。每个数字应该只打印一次。打印数字时,用空格分隔它们。
示例
输入 #1
1 2 1 1 S 1 1 M
输出 #1
0
输入 #2
3 3 1 2 S 1 3 M 2 3 S
输出 #2
2 2 1
输入 #3
5 6 1 1 S 1 2 M 1 3 S 1 4 M 1 5 M 2 2 S
输出 #3
-1
注意
如果一条路径上的所有小屋都成对不同,则该路径被称为简单路径。