CF662B.Graph Coloring

You are given an undirected graph that consists of n vertices and m edges. Initially, each edge is colored either red or blue. Each turn a player picks a single vertex and switches the color of all edges incident to it. That is, all red edges with an endpoint in this vertex change the color to blue, while all blue edges with an endpoint in this vertex change the color to red.

Find the minimum possible number of moves required to make the colors of all edges equal.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向图。初始时，每条边被染成红色或蓝色。每一轮，一名玩家选择一个顶点，并翻转所有与该顶点关联的边的颜色：即所有以该顶点为端点的红边变为蓝边，所有以该顶点为端点的蓝边变为红边。

求使所有边颜色相同的最少操作次数。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of vertices and edges, respectively.

The following m lines provide the description of the edges, as the i-th of them contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — the indices of the vertices connected by the i-th edge, and a character c__i () providing the initial color of this edge. If c__i equals 'R', then this edge is initially colored red. Otherwise, c__i is equal to 'B' and this edge is initially colored blue. It's guaranteed that there are no self-loops and multiple edges.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100\,000$），分别表示顶点数和边数。

接下来的 $m$ 行描述各条边；其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$），表示第 $i$ 条边所连接的两个顶点的编号，以及一个字符 $c_i$（），表示该边的初始颜色。若 $c_i$ 等于 'R'，则该边初始为红色；否则 $c_i$ 等于 'B'，该边初始为蓝色。保证图中不存在自环和重边。

If there is no way to make the colors of all edges equal output  - 1 in the only line of the output. Otherwise first output k — the minimum number of moves required to achieve the goal, then output k integers _a_1, _a_2, ..., a__k, where a__i is equal to the index of the vertex that should be used at the i-th move.

If there are multiple optimal sequences of moves, output any of them.

如果无法使所有边的颜色相同，则在输出的唯一一行中输出 -1。否则，首先输出 k —— 达成目标所需的最少操作次数，然后输出 k 个整数 a_1, a_2, ..., a_k，其中 a_i 表示第 i 次操作中应使用的顶点的编号。

如果存在多个最优操作序列，输出其中任意一个即可。