We can do this in $\mathcal{O}(1)$ time. Define $\texttt{beat}[i][j]$ to be $\texttt{true}$ if symbol $i$ wins against symbol $j$, and false otherwise. If Bessie reveals symbols $a$ and $b$, and Elsie reveals symbols $x$ and $y$, then Bessie is guaranteed to win if $a$ beats both $x$ and $y$ (i.e. $\texttt{beat[a][x] and beat[a][y]}$) or if $b$ beats both $x$ and $y$ (i.e. $\texttt{beat[b][x] and beat[b][y]}$).

For subtask 1, we can use brute-force. For every game, loop through every combination of symbols Bessie can play, and for each one, check to see if Bessie can guarantee a win. This runs in $\mathcal{O}(N^2M)$.

N, M = map(int, input().split())
data = [input() for _ in range(N)]
beat = [[0] * N for _ in range(N)]
 
for i in range(N):
    for j in range(i):
        if data[i][j] != "D":
            if data[i][j] == "W":
                beat[i][j] = 1
            else:
                beat[j][i] = 1
 
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    ans = 0
    for a in range(N):
        for b in range(N):
            ans += (beat[a][x] and beat[a][y]) or (beat[b][x] and beat[b][y])
    print(ans)

In C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<string> data(N);
    for (int i = 0; i < N; i++) {
        cin >> data[i];
    }

    vector<vector<int>> beat(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (data[i][j] != 'D') {
                if (data[i][j] == 'W') {
                    beat[i][j] = 1;
                } else {
                    beat[j][i] = 1;
                }
            }
        }
    }

    for (int q = 0; q < M; q++) {
        int x, y;
        cin >> x >> y;
        x--; 
        y--;

        long long ans = 0;
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                if ((beat[a][x] && beat[a][y]) || (beat[b][x] && beat[b][y])) {
                    ans++;
                }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

For subtask 2, this is too slow. Since $N$ and $M$ are $3000$, we can guess that the solution's time complexity might be something like $\mathcal{O}(NM)$. Let's see if we can get rid of one of the for loops.

To achieve our desired complexity of $\mathcal{O}(NM)$, we can loop through all $N$ symbols for every game. Consider a single game between Bessie and Elsie. Let's loop through the symbol Bessie reveals in her left hoof, $a$. We want to answer the following question in $\mathcal{O}(1)$: Which symbols $b$ can Bessie reveal in her right foot that will guarantee a win against Elsie?

Let's say Elsie plays symbols $x$ and $y$. There are two cases to consider.

Case 1: If $a$ beats both $x$ and $y$, i.e. $\texttt{beat[a][x] and beat[a][y]}$, then Bessie can reveal any symbol $b$ in her right hoof and she will guarantee a win against Elsie by playing symbol $a$. In this case, the answer to our question is $N$.

Case 2: If $a$ is unable to beat both $x$ and $y$, then Bessie must reveal a symbol $b$ in her right hoof that can beat both $x$ and $y$ in order to guarantee a win against Elsie. In this case, the answer to our question is the number of symbols that beat both $x$ and $y$.

Case 1 can be determined in $\mathcal{O}(1)$ time, but Case 2 requires $\mathcal{O}(N)$ time to compute since we have to loop through all $N$ symbols to count the number of symbols that beat both $x$ and $y$. If we have to do this for every symbol $a$ that is unable to beat both $x$ and $y$, doesn't this mean our final time complexity is $\mathcal{O}(N^2M)$?

As it turns out, we don't have to do this for every symbol $a$. Instead, we only have to do this once per game, and then we can reuse our computed result for all symbols $a$. So, for every game, we need to do an $\mathcal{O}(N)$ precomputation to count the number of symbols that beat both $x$ and $y$, then we have to loop through all symbols $a$ that Bessie can reveal in her left hoof, which is $\mathcal{O}(N)$. Our final time complexity is therefore $\mathcal{O}(M \cdot (N + N)) = \mathcal{O}(NM)$.

N, M = map(int, input().split())
data = [input() for _ in range(N)]
beat = [[0] * N for _ in range(N)]
 
for i in range(N):
    for j in range(i):
        if data[i][j] != "D":
            if data[i][j] == "W":
                beat[i][j] = 1
            else:
                beat[j][i] = 1
 
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())

    # Number of symbols b that can beat both x and y
    winning = 0
    for b in range(N):
        winning += beat[b][x] and beat[b][y]
    
    ans = 0
    for a in range(N):
        if beat[a][x] and beat[a][y]:
            # Case 1: The symbol in Bessie's left hoof beats both symbols x and y
            # Bessie can play any symbol in her right hoof
            ans += N
        else:
            # Case 2: The symbol in Bessie's left hoof cannot beat both symbols x and y
            # Bessie must play a symbol that can beat both x and y in her right hoof
            ans += winning

    print(ans)

In C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    
    vector<string> data(N);
    for (int i = 0; i < N; i++) {
        cin >> data[i];
    }
    
    vector<vector<int>> beat(N, vector<int>(N, 0));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (data[i][j] != 'D') {
                if (data[i][j] == 'W')
                    beat[i][j] = 1;
                else
                    beat[j][i] = 1;
            }
        }
    }
    
    while (M--) {
        int x, y;
        cin >> x >> y;
        x--; 
        y--;
        
        // Number of symbols b that can beat both x and y
        int winning = 0;
        for (int b = 0; b < N; b++) {
            if (beat[b][x] && beat[b][y])
                winning++;
        }
        
        int ans = 0;
        for (int a = 0; a < N; a++) {
            if (beat[a][x] && beat[a][y]) {
                // Case 1: The symbol in Bessie's left hoof beats both symbols x and y
                // Bessie can play any symbol in her right hoof
                ans += N;
            } else {
                // Case 2: The symbol in Bessie's left hoof cannot beat both symbols x and y
                // Bessie must play a symbol that can beat both x and y in her right hoof
                ans += winning;
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

You can also solve this problem with a bit of math. For every game, let $w$ be the number of "winning" symbols -- i.e. the number of symbols that can beat both symbols Elsie reveals, $x$ and $y$. In the code above, $w = \texttt{winning}$.

It turns out that the number of pairs of symbols $(a, b)$ that Bessie can reveal to guarantee a win is equal to $N^2 - (N-w)^2$. We arrive at this solution via complementary counting: We'll count the number of pairs that make it impossible to guarantee Bessie a win and subtract that from the total number of pairs Bessie can play. The result is the number of pairs Bessie can play that does guarantee a win.

How many pairs make it impossible to guarantee a win for Bessie? Well, neither symbol $a$ nor $b$ can be a "winning" symbol, otherwise Bessie could just play that to guarantee a win. If there are $w$ winning symbols and $N$ symbols total, the number of non-winning symbols is $N - w$. $a$ and $b$ must both be a non-winning symbol, so the number of pairs of symbols $(a, b)$ that make it impossible to guarantee a win for Bessie is $(N-w)^2$. Finally, the total number of pairs Bessie can play is $N^2$ (since there are $N$ options for each of the left / right hooves), so our final answer is $N^2 - (N-w)^2$.

Another way you could have arrived at this formula is to count the number of symbols that satisfy Case 1 and Case 2. Case 1, which is when $a$ beats both $x$ and $y$, is precisely the number of winning symbols. Every symbol is either Case 1 or Case 2, so if there are $w$ winning symbols, then there are $w$ symbols in Case 1 and $N - w$ symbols in Case 2.

For every symbol in Case 1, we add $N$ to our answer, so we get $N \cdot w$ in total. For every symbol in Case 2, we add $w$ to our answer, so we get $(N - w) \cdot w$ in total.

Summing the two, we get $Nw + (N - w) \cdot w = 2Nw - w^2 = N^2 - N^2 + 2Nw - w^2 = N^2 - (N^2 - 2Nw + w^2) = N^2 - (N - w)^2$.

N, M = map(int, input().split())
data = [input() for _ in range(N)]
beat = [[0] * N for _ in range(N)]
 
for i in range(N):
    for j in range(i):
        if data[i][j] != "D":
            if data[i][j] == "W":
                beat[i][j] = 1
            else:
                beat[j][i] = 1
 
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())

    # Number of symbols b that can beat both x and y
    winning = 0
    for b in range(N):
        winning += beat[b][x] and beat[b][y]
    
    total_playable_pairs = N ** 2
    losing_pairs = (N-winning) ** 2
    
    print(total_playable_pairs - losing_pairs)

In C++:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> data(N);
    for (int i = 0; i < N; i++) {
        cin >> data[i];
    }
    vector<vector<int>> beat(N, vector<int>(N, 0));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (data[i][j] != 'D') {
                if (data[i][j] == 'W')
                    beat[i][j] = 1;
                else
                    beat[j][i] = 1;
            }
        }
    }
    
    while (M--) {
        int x, y;
        cin >> x >> y;
        x--; 
        y--;
        
        // Number of symbols b that can beat both x and y
        int winning = 0;
        for (int b = 0; b < N; b++) {
            if (beat[b][x] && beat[b][y])
                winning++;
        }
        
        int total_playable_pairs = N * N;
        int losing_pairs = (N - winning) * (N - winning);
        
        cout << total_playable_pairs - losing_pairs << "\n";
    }
    return 0;
}