CF1288F.Red-Blue Graph

You are given a bipartite graph: the first part of this graph contains $n_1$ vertices, the second part contains $n_2$ vertices, and there are $m$ edges. The graph can contain multiple edges.

Initially, each edge is colorless. For each edge, you may either leave it uncolored (it is free), paint it red (it costs $r$ coins) or paint it blue (it costs $b$ coins). No edge can be painted red and blue simultaneously.

There are three types of vertices in this graph — colorless, red and blue. Colored vertices impose additional constraints on edges' colours:

• for each red vertex, the number of red edges indicent to it should be strictly greater than the number of blue edges incident to it;
• for each blue vertex, the number of blue edges indicent to it should be strictly greater than the number of red edges incident to it.

Colorless vertices impose no additional constraints.

Your goal is to paint some (possibly none) edges so that all constraints are met, and among all ways to do so, you should choose the one with minimum total cost.

给你一个二分图：该图的第一部分包含 $n_1$ 个顶点，第二部分包含 $n_2$ 个顶点，共有 $m$ 条边。图中可能含有多重边。

初始时，每条边均无颜色。对于每条边，你可以选择：保持其无色（即免费），将其涂成红色（花费 $r$ 枚硬币），或将其涂成蓝色（花费 $b$ 枚硬币）。任意一条边不能同时被涂成红色和蓝色。

图中的顶点分为三类：无色顶点、红色顶点和蓝色顶点。带颜色的顶点对关联边的颜色施加额外约束：

• 对每个红色顶点，与其关联的红色边的数量必须严格大于与其关联的蓝色边的数量；
• 对每个蓝色顶点，与其关联的蓝色边的数量必须严格大于与其关联的红色边的数量。

无色顶点不施加任何额外约束。

你的目标是给某些（可能为零条）边染色，使得所有约束均被满足；在所有满足约束的方案中，你应选择总花费最小的一种。

The first line contains five integers $n_1$, $n_2$, $m$, $r$ and $b$ ($1 \le n_1, n_2, m, r, b \le 200$) — the number of vertices in the first part, the number of vertices in the second part, the number of edges, the amount of coins you have to pay to paint an edge red, and the amount of coins you have to pay to paint an edge blue, respectively.

The second line contains one string consisting of $n_1$ characters. Each character is either U, R or B. If the $i$-th character is U, then the $i$-th vertex of the first part is uncolored; R corresponds to a red vertex, and B corresponds to a blue vertex.

The third line contains one string consisting of $n_2$ characters. Each character is either U, R or B. This string represents the colors of vertices of the second part in the same way.

Then $m$ lines follow, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i \le n_1$, $1 \le v_i \le n_2$) denoting an edge connecting the vertex $u_i$ from the first part and the vertex $v_i$ from the second part.

The graph may contain multiple edges.

第一行包含五个整数 $n_1$、$n_2$、$m$、$r$ 和 $b$（$1 \le n_1, n_2, m, r, b \le 200$），分别表示二分图第一部分的顶点数、第二部分的顶点数、边数、将一条边染成红色所需支付的金币数，以及将一条边染成蓝色所需支付的金币数。

第二行包含一个由 $n_1$ 个字符组成的字符串。每个字符为 U、R 或 B。若第 $i$ 个字符为 U，则第一部分的第 $i$ 个顶点未染色；R 表示该顶点为红色，B 表示该顶点为蓝色。

第三行包含一个由 $n_2$ 个字符组成的字符串。每个字符为 U、R 或 B。该字符串以相同方式表示第二部分各顶点的颜色。

接下来是 $m$ 行，其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i \le n_1$，$1 \le v_i \le n_2$），表示连接第一部分中顶点 $u_i$ 与第二部分中顶点 $v_i$ 的一条边。

该图可能包含重边。

If there is no coloring that meets all the constraints, print one integer $-1$.

Otherwise, print an integer $c$ denoting the total cost of coloring, and a string consisting of $m$ characters. The $i$-th character should be U if the $i$-th edge should be left uncolored, R if the $i$-th edge should be painted red, or B if the $i$-th edge should be painted blue. If there are multiple colorings with minimum possible cost, print any of them.

如果不存在满足所有约束条件的染色方案，则输出一个整数 $-1$。

否则，输出一个整数 $c$，表示染色的总代价，以及一个长度为 $m$ 的字符串。该字符串的第 $i$ 个字符应为：U（表示第 $i$ 条边不染色）、R（表示第 $i$ 条边染红色）或 B（表示第 $i$ 条边染蓝色）。若存在多种具有最小可能代价的染色方案，输出任意一种即可。