Red-Blue Graph
Contest: Educational Codeforces Round 80 (Rated for Div. 2)
Difficulty rating: 2900
Tags: constructive algorithms, flows

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Example input:
3 2 6 10 15
RRB
UB
3 2
2 2
1 2
1 1
2 1
1 1

Example output:
35
BUURRU

Example input:
3 1 3 4 5
RRR
B
2 1
1 1
3 1

Example output:
-1

Editorial:
A lot of things in this problem may tell us that we should try thinking about a flow solution. Okay, let's try to model the problem as a flow network.
First of all, our network will consist of vertices and edges of the original graph. We somehow have to denote "red", "blue" and "colorless" edges; we will do it as follows: each edge of the original graph corresponds to a bidirectional edge with capacity $$$1$$$ in the network; if the flow goes from the left part to the right part along the edge, it is red; if the flow goes from right to left, it is a blue edge; and if there is no flow along the edge, it is colorless.
Okay, we need to impose some constraints on the vertices. Consider some vertex $$$v$$$ from the left part. Each red edge incident to it transfers one unit of flow from it to some other vertex, and each blue edge incident to it does the opposite. So, the difference between the number of blue and red edges incident to $$$v$$$ is the amount of excess flow that has to be transfered somewhere else. If $$$v$$$ is colorless, there are no constraints on the colors of edges, so this amount of excess flow does not matter — to model it, we can add a directed edge from source to $$$v$$$ with infinite capacity, and a directed edge from $$$v$$$ to sink with infinite capacity. What if $$$v$$$ is red? At least one unit of flow should be transfered to it; so we add a directed edge from the source to $$$v$$$ with infinite capacity such that there should be at least one unit of flow along it. And if $$$v$$$ is blue, we need to transfer at least one unit of excess flow from it — so we add a directed edge from $$$v$$$ to the sink with infinite capacity such that there is at least one unit of flow along it. The colors of the vertices in the right part can be modeled symmetrically.
How to deal with edges such that there should be some flow along them? You may use classic "flows with demands" approach from here: https://cp-algorithms.com/graph/flow_with_demands.html. Or you can model it with the help of the costs: if the flow along the edge should be between $$$l$$$ and $$$r$$$, we can add two edges: one with capacity $$$l$$$ and cost $$$k$$$ (where $$$k$$$ is a negative number with sufficiently large absolute value, for example, $$$-10^9$$$), and another with capacity $$$r - l$$$ and cost $$$0$$$.
Okay, now we know how to find at least one painting. How about finding the cheapest painting that meets all the constraints? One of the simplest ways to do it is to impose costs on the edges of the original graph: we can treat each edge of the original graph as a pair of directed edges, one going from left to right with capacity $$$1$$$ and cost $$$r$$$, and another going from right to left with capacity $$$1$$$ and cost $$$b$$$.