CF141E Clearing Up

在圣诞老人和他的助手精灵送完所有礼物并实现了所有愿望之后，他们回到了北极，却发现北极被大雪覆盖了。他们都很疲惫，于是决定只清除连接小屋的道路上的积雪。北极有 $n$ 个小屋，通过 $m$ 条道路相连。道路是双向的。 精灵提出分工：圣诞老人负责清理宽敞的道路，精灵负责踩实狭窄的小路。他们为每条道路决定由谁来清理：圣诞老人或精灵。为尽量减少大家的工作量，他们决定选择需要清理的道路，使得以下条件同时满足： - 任意两个小屋之间，沿被清理的道路应恰好存在一条简单路径； - 圣诞老人和精灵各自清理的道路数量相等。 那么，圣诞老人和他的助手精灵应选择清理哪些道路呢？

第一行包含两个正整数 $n$ 和 $m$（$1 \leq n \leq 10^{3}$，$1 \leq m \leq 10^{5}$），分别表示小屋数和道路数。接下来的 $m$ 行，每行描述一条道路，包含两个小屋编号 $x$ 和 $y$（$1 \leq x, y \leq n$），以及负责清理这条道路的人（"S" 表示精灵，"M" 表示圣诞老人）。每条道路都是双向的。注意，可能存在两小屋之间有多条道路，也可能有某条道路起止于同一个小屋。

如果无法按照规则选择需要清理的道路，则输出一行“-1”（不含引号）。否则，第一行输出需要清理的道路数，第二行输出这些道路的编号（按输入顺序从 $1$ 开始编号）。编号可以按任意顺序输出，每个编号只能出现一次，编号之间用空格分隔。

一条路径称为简单路径，如果其中经过的小屋两两不同。 由 ChatGPT 5 翻译