#include #include #include #include #include #include using namespace std; bool findPathAndUpdate(const vector> &graph, const vector> &capacity, vector> &flow, vector &previous, const string &verticesStates, queue &q) { // Find unsaturated path using BFS q = {}; fill(previous.begin(), previous.end(), -1); // Set all vertices to non-visited state for (int v = 0; v < graph.size(); v++) { if (verticesStates[v] == 'W') { q.push(v); previous[v] = -2; // Set sources as already visited } } int current; int reserve; int endSink = -1; while (!q.empty()) { current = q.front(); if (verticesStates[current] == 'L') { endSink = current; break; } q.pop(); for (int neighbour : graph[current]) { reserve = capacity[current][neighbour] - flow[current][neighbour] + flow[neighbour][current]; if (previous[neighbour] == -1 && reserve > 0) { previous[neighbour] = current; q.push(neighbour); } } } if (endSink == -1) { return false; } // Compute reserve of the found path current = endSink; int prevVertex; int8_t pathReserve = 127; int8_t edgeReserve; while (verticesStates[current] != 'W') { prevVertex = previous[current]; edgeReserve = capacity[prevVertex][current] - flow[prevVertex][current] + flow[current][prevVertex]; pathReserve = min(pathReserve, edgeReserve); current = prevVertex; } // Update the flows current = endSink; int8_t delta; // Flow subtracted from the opposite direction while (verticesStates[current] != 'W') { prevVertex = previous[current]; delta = min(flow[current][prevVertex], pathReserve); flow[prevVertex][current] += pathReserve - delta; flow[current][prevVertex] -= delta; current = prevVertex; } return true; } signed main(signed argc, char *argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; string systemsStr; cin >> n >> systemsStr >> m; vector> graph(n); vector> capacity(n, vector(n)), flow(n, vector(n)); for (int i = 0; i < m; i++) { int u_i, v_i; cin >> u_i >> v_i; graph[u_i].push_back(v_i); graph[v_i].push_back(u_i); capacity[u_i][v_i] = 1; capacity[v_i][u_i] = 1; } vector previous(n, -1); queue q; while (findPathAndUpdate(graph, capacity, flow, previous, systemsStr, q)) { } for (int i = 0; i < n; i++) { if (systemsStr[i] == 'W') cout << 'W'; else if (systemsStr[i] == 'L') cout << 'L'; else { if (previous[i] == -1) cout << 'L'; else cout << 'W'; } } cout << endl; return 0; }