← 返回题目列表

Codeforces · 141/E

E. 清理

中文机器翻译题面 查看原题

圣诞老人和他的助手精灵送完所有的礼物并实现了所有的愿望后,他们回到了北极,却发现北极已经被白雪覆盖了。两人都累了,决定只清除连接小屋的道路上的积雪。北极有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

注意

如果一条路径上的所有小屋都成对不同,则该路径被称为简单路径。