← 返回题目列表

Codeforces · 1288/F

F. 红蓝图

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

给定一个二部图:该图的第一部分包含 $$$n_1$$$ 个顶点,第二部分包含 $$$n_2$$$ 个顶点,并且有 $$$m$$$ 个边。该图可以包含多条边。

最初,每条边缘都是无色的。对于每条边,您可以将其保留为无色(免费)、将其涂成红色(需要花费 $$$r$$$ 硬币)或将其涂成蓝色(需要花费 $$$b$$$ 硬币)。没有边可以同时涂成红色和蓝色。

该图中共有三种类型的顶点 - 无色、红色和蓝色。彩色顶点对边的颜色施加了额外的限制:

- 对于每个红色顶点,与其相关的红色边的数量应严格大于与其相关的蓝色边的数量;
- 对于每个蓝色顶点,与其相关的蓝色边的数量应严格大于与其相关的红色边的数量。

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

您的目标是绘制一些(可能没有)边缘,以便满足所有约束,并且在所有方法中,您应该选择总成本最小的一种。

输入

第一行包含五个整数 $$$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$$$。

该图可能包含多条边。

输出

如果没有满足所有约束的着色,则打印一个整数$$$-1$$$。

否则,打印一个整数 $$$c$$$ 表示着色的总成本,以及一个由 $$$m$$$ 字符组成的字符串。如果第 $$$i$$$ 个边缘应保持不着色,则第 $$$i$$$ 个字符应为 U;如果应将第 $$$i$$$ 个边缘涂成红色,则第 $$$i$$$ 个字符应为 R;如果应将第 $$$i$$$ 个边缘涂成蓝色,则第 $$$i$$$ 个字符应为 B。如果有多种颜色且成本尽可能最低,则打印其中任何一种。

示例

输入 #1

3 2 6 10 15
RRB
UB
3 2
2 2
1 2
1 1
2 1
1 1

输出 #1

35
BUURRU

输入 #2

3 1 3 4 5
RRR
B
2 1
1 1
3 1

输出 #2

-1

输入 #3

3 1 3 4 5
URU
B
2 1
1 1
3 1

输出 #3

14
RBB