给定一个由 n 个顶点和 m 个边组成的无向图。最初,每条边都被着色为红色或蓝色。每个回合,玩家都会选择一个顶点并切换与其相关的所有边的颜色。也就是说,端点位于该顶点的所有红色边都会将颜色更改为蓝色,而端点位于该顶点的所有蓝色边都会将颜色更改为红色。
找出使所有边的颜色相等所需的最小可能移动次数。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100 000) - 分别是顶点和边的数量。
接下来的 m 行提供了边的描述,因为其中的第 i 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 由第 i 条边连接的顶点的索引,以及提供该边的初始颜色的字符 ci ($${ c _ { i } \in \{ B, R \} }$$)。如果 ci 等于“R”,则该边最初颜色为红色。否则,ci 等于“B”,并且该边缘最初为蓝色。保证不存在自环和重边。
输出
如果无法使所有边缘的颜色相等,则输出的唯一行中输出 - 1。否则首先输出 k - 达到目标所需的最小移动次数,然后输出 k 个整数 a1, a2, ..., ak,其中 ai 等于第 i 次移动时应使用的顶点的索引。
如果存在多个最佳移动序列,则输出其中任何一个。
示例
输入 #1
3 3 1 2 B 3 1 R 3 2 B
输出 #1
1 2
输入 #2
6 5 1 3 R 2 3 R 3 4 B 4 5 R 4 6 R
输出 #2
2 3 4
输入 #3
4 5 1 2 R 1 3 R 2 3 B 3 4 B 1 4 B
输出 #3
-1