1288F - Red-Blue Graph - CodeForces Solution

               //  ॐ
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
typedef pair<int,int>       pii;
typedef pair<ll,ll>       pll;
typedef vector<ll> vll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
#define pb              push_back 
#define Sort(a)         sort(a.begin(),a.end())
#define ff                  first
#define ss                  second 
const int N = 1e3 + 5;
const int f = 1e8 + 7;

struct edge
{
    int y, c, f, cost;
    edge() {};
    edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
};

int sr,sn,osr,osn;

string s1,s2;
vector<edge> ed;
vector<pii> eds;
vvi g(N);

void add(int x, int y, int c, int ct){
    g[x].pb(ed.size());
    ed.pb({y,c,0,ct});
    g[y].pb(ed.size());
    ed.pb({x,0,0,-ct});
}

void addcond(int x, int y, int c, int d){
    int lf = c - d;
    if(d){
        add(sr,y,d,0);
        add(x,sn,d,0);
    }
    if(lf){
        add(x,y,lf,0);
    }
}

bool reducable(int n) {
    vector<int> d(n, f);
    d[sr] = 0;
    vector<bool> inq(n, false);
    queue<int> q;
    q.push(sr);
    vector<int> p(n, -1);
    vector<int> pe(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (auto x : g[u]) {
            auto e = ed[x]; int v = e.y;
            if (e.c-e.f > 0 && d[v] > d[u] + e.cost) {
                d[v] = d[u] + e.cost;
                p[v] = u; pe[v] = x;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }

    if(p[sn] == -1)
        return false;
    int cur = sn;
    while(cur != sr)
    {
        ed[pe[cur]].f++;
        ed[pe[cur] ^ 1].f--;
        cur = p[cur];
    }
    return true;

}

void solve(){
    int n1,n2,m,r,b;
    cin>>n1>>n2>>m>>r>>b;
    cin>>s1>>s2;
    for (int i = 0; i < m; ++i){
        int x,y; 
        cin>>x>>y;
        eds.pb({x,y});
        add(x,y+n1,1,r);
        add(y+n1,x,1,b);
    }

    osr = n1+n2+1; osn = n1+n2+2;
    sr = 0; sn = n1 + n2 + 3;

    for (int i = 1; i <= n1; ++i){
        if(s1[i-1]=='R'){
            addcond(osr,i,m,1);
        }else if(s1[i-1]=='B'){
            addcond(i,osn,m,1);
        }else{
            add(osr,i,m,0);
            add(i,osn,m,0);
        }
    }

    for (int i = 1; i <= n2; ++i){
        if(s2[i-1]=='R'){
            addcond(i+n1,osn,m,1);
        }else if(s2[i-1]=='B'){
            addcond(osr,i+n1,m,1);
        }else{
            add(osr,i+n1,m,0);
            add(i+n1,osn,m,0);
        }
    }

    add(osn, osr, f, 0);

    while(reducable(sn+1));

    vvi fl(n1+1,vi(n2+1,0));
    for (int i = 1; i <= n1; ++i){
        for (auto x : g[i]) {
            auto e = ed[x]; int v = e.y;
            if( v > n1 && v <= n2+n1 ){
                fl[i][v-n1] += e.f;
            }
        }
    }

    for(auto &x: g[sr]){
        auto e = ed[x];
        if(e.c-e.f){
            cout<<"-1\n"; return;
        }
    }

    string ans; int tot = 0;
    for(auto &[x,y]: eds){
        if(fl[x][y]>0){
            fl[x][y]--;
            tot += r;
            ans.pb('R');
        }else if(fl[x][y]<0){
            fl[x][y]++;
            tot += b;
            ans.pb('B');
        }else ans.pb('U');
    }

    cout<<tot<<"\n"<<ans;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t=1;
    // cin>>t;
    while(t--)
        solve();
 
}