← 返回题目列表

Codeforces · 662/B

B. 图形着色

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

给定一个由 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