部屋 \(u,\) 部屋 \(v,\) 青木君か高橋君のいずれかである \(t\) からなる \(3\) つ組 \((u,v,t)\) を頂点とするグラフを考えます。

元の建物に部屋 \(u\) から部屋 \(x\) へ向かう廊下があるとき、かつそのときに限り \((u,v,\) 青木君\()\) から \((x,v,\) 高橋君\()\) への辺を張り、元の建物に部屋 \(v\) から部屋 \(x\) へ向かう廊下があるとき、かつそのときに限り \((u,v,\) 高橋君\()\) から \((u,x,\) 青木君\()\) への辺を張ります。 また、\((u,v,\) 高橋君\()\) と \((u,v,\) 青木君\()\) の間に相互に辺を張ります。

すると、この問題はこのグラフを用いて次のように言い換えることができます。

はじめ、グラフ上のある頂点に駒が置かれている。 高橋君と青木君は次の操作を繰り返す。

• 駒が置かれている頂点の第三要素であるほうが、駒が置かれている頂点から辺が伸びている頂点をひとつ選び、そこに駒を動かす。

グラフのいくつかの頂点は青木君頂点である。 駒が青木君頂点に置かれたとき、直ちにゲームが終了し、青木君の勝利となる。 青木君が勝つか（青木君が適切に行動したとき、高橋君の行動によらず有限回で駒を青木君頂点に移動させられるか）を判定せよ。

ここで、駒がはじめに置かれている頂点は \((S _ j,R _ j,\) 高橋君\()\) であり、青木君頂点は \((u,u,t)\) と表されるすべての頂点です（\(3\) つめの要素が青木君である頂点ではないことに注意してください）。

これは、次のような探索によって判定することができます。

1. はじめ、すべての青木君頂点をキューに追加する。
2. キューが空でなくなるまで、以下の操作を続ける。
   1. キューから頂点を取り出し、\(v\) とする。
   2. \(v\) の結果を「青木君が勝つ」とする。
   3. \(v\) へ辺が伸びているすべての頂点 \(u\) について、以下を行う。
      1. \(u\) の第三要素が高橋君なら、\(u\) から辺が伸びるすべての頂点の結果が「青木君が勝つ」であるとき、キューに \(u\) を追加する。
      2. \(u\) の第三要素が青木君なら、キューに \(u\) を追加する。
3. 結果がわかっていない頂点の結果をすべて「青木君が勝てない」とする。

このように、ゲームの結果を決着がついた状態から探索していく手法は後退解析と呼ばれます。

あとは、すでに探索した頂点の扱いや、第三要素が高橋君であるときにキューへ追加する条件を適切に管理することで、それぞれの頂点に対してその頂点に駒が置かれている状態からゲームを開始したときの結果を十分高速に得ることができます。

時間計算量は、言い換えたあとのグラフの頂点数が \(O(N ^ 2)\) 、辺の本数が \(O(N ^ 3)\) であるので、全体で \(O(N ^ 3)\) などとなります。

実装例は以下のようになります。

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

int main() {
    int N, M;
    cin >> N >> M;

    // 辺を逆向きに管理する
    vector<vector<int>> rev_edge(N);
    // (u, v, t) をキューに入れるために何回見る必要があるか
    // 青木君の頂点なら 1 回、高橋君の頂点なら (出次数) 回
    vector remain(N, vector(N, vector{1, 1}));
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v; // 0-indexed にしておく
        rev_edge[v].emplace_back(u); // 逆辺を追加して
        for (int w = 0; w < N; ++w) {
            ++remain[u][w][0]; // 出次数を増やす
        }
    }
    // その場に留まってもよい
    for (int u = 0; u < N; ++u) {
        rev_edge[u].emplace_back(u);
    }

    vector answer(N, vector(N, vector{1, 1}));
    // 後退解析で勝敗を求める
    queue<tuple<int, int, int>> q;
    // 青木君が勝っている頂点をキューに入れる
    for (int u = 0; u < N; ++u) {
        q.emplace(u, u, 0);
        remain[u][u][0] = 0;
        q.emplace(u, u, 1);
        remain[u][u][1] = 0;
    }
    while (!q.empty()) {
        auto [now_s, now_r, turn] = q.front();
        q.pop();
        answer[now_s][now_r][turn] = 0;
        // どちらの手番かで場合分け
        if (turn) {
            for (int next : rev_edge[now_s]) {
                if (--remain[next][now_r][1 - turn] == 0) {
                    q.emplace(next, now_r, 1 - turn);
                }
            }
        } else {
            for (int next : rev_edge[now_r]) {
                if (--remain[now_s][next][1 - turn] == 0) {
                    q.emplace(now_s, next, 1 - turn);
                }
            }
        }
    }
    
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int s, r;
        cin >> s >> r;
        --s;
        --r; // 0-indexed にして
        // 前計算した結果を返す
        cout << (answer[s][r][0] ? "YES" : "NO") << endl;
    }
    return 0;
}