Overview

This problem is a two-player game on a directed graph where Takahashi (the evader) and Aoki (the pursuer) know each other’s positions and act optimally. We need to determine the winner of the game.

For each query, we determine whether Takahashi can “escape forever (Takahashi wins/draws, including repetition)” or “will inevitably be caught (Aoki wins).” Since the number of states is sufficiently small, we can use Backward Induction, which determines outcomes by working backwards from terminal states, to efficiently precompute the results for all initial positions.

---

Analysis

1. Definition of Game States

The progress of the game can be completely described by the following three pieces of information: - Takahashi’s current position: \(u\) - Aoki’s current position: \(v\) - Current turn: \(t\) (\(t = 0\): Takahashi’s turn, \(t = 1\): Aoki’s turn)

Since the number of rooms \(N\) is at most \(500\), the total number of states is \(N \times N \times 2 \le 500 \times 500 \times 2 = 500,000\). This is small enough for a computer to store and explore all states.

2. Conditions for Determining the Outcome

Based on the game’s objective, each state \((u, v, t)\) is classified as one of the following: - Aoki wins (caught): If Aoki plays optimally, he can always catch Takahashi within a finite number of turns. - Takahashi wins (escapes): If Takahashi plays optimally, he will never be caught regardless of how Aoki moves.

In this approach, we determine “states where Aoki wins” by working backwards (backward induction).

① Initial Determined States (Base Cases)

States where Takahashi and Aoki are in the same room (\(u = v\)) are Aoki’s win regardless of the turn \(t\), since Takahashi is already caught.

② Backward Transitions from Aoki’s Turn (\(t = 1\))

On Aoki’s turn, Aoki can either “stay” or “move to an adjacent room.” Since Aoki wants to transition to a state where he wins, if among the candidate destinations there exists at least one state determined as “Aoki’s win,” then the state before the move is also “Aoki’s win.”

③ Backward Transitions from Takahashi’s Turn (\(t = 0\))

On Takahashi’s turn, Takahashi can either “stay” or “move to an adjacent room.” Since Takahashi wants to avoid being caught, he tries to escape to a state where “Aoki cannot win.” Therefore, only when all candidate destinations (staying or moving to adjacent rooms) are “Aoki’s win” does the state before the move also become “Aoki’s win.”

---

Algorithm

We implement the backward induction using a procedure similar to Breadth-First Search (BFS) with a queue.

1. Initialization of States and Degrees

• win[u][v][t]: true if state \((u, v, t)\) is “Aoki’s win.”
• deg[u][v]: The number of choices Takahashi has from state \((u, v, 0)\) (Takahashi’s turn).
  • Since Takahashi can either “stay in the current room \(u\) (1 option)” or “move to an adjacent room (out-degree options),” the initial value is \(1 + (\text{out-degree of room } u)\).

2. Queue Initialization

For all \(i \, (1 \le i \le N)\), set win[i][i][0] = true and win[i][i][1] = true, and add these states to the queue.

3. Updating Transitions Using the Queue

Dequeue a determined state \((u, v, t)\) and update the “one-step-previous states” that could have transitioned to this state.

• Case 1: \(t = 0\) (Working backwards from Takahashi’s turn)

  • One step before was Aoki’s turn (\(t = 1\)).
  • Aoki must have been at a position (\(v_{prev}\)) from which he could transition to \((u, v, 0)\) on the next turn.
  • \(v_{prev}\) is either \(v\) itself (staying) or a room with a directed edge \(v_{prev} \to v\) (adjacent vertices in the reverse graph revG[v]).
  • These states \((u, v_{prev}, 1)\) become states where Aoki can win by moving appropriately, so we set win[u][v_{prev}][1] = true and add them to the queue.

• Case 2: \(t = 1\) (Working backwards from Aoki’s turn)

  • One step before was Takahashi’s turn (\(t = 0\)).
  • We consider the situation where Takahashi has no choice but to select \((u, v, 1)\) as a transition destination.
  • If Takahashi moved from \(u_{prev}\) to \(u\) (or stayed at \(u_{prev}\)) to transition to \((u, v, 1)\), then one option has been eliminated from state \((u_{prev}, v, 0)\).
  • Therefore, we decrement deg[u_{prev}][v] by 1.
  • If deg[u_{prev}][v] becomes 0, it means no matter which move Takahashi chooses, he can only reach “Aoki’s win” states (there is no escape route). In this case, we set win[u_{prev}][v][0] = true and add it to the queue.

4. Answering Queries

Once the precomputation is complete, for each query \((S_j, R_j)\), we output NO if win[S_j][R_j][0] is true, and YES (there exists an escape path or loop) if it is false, in \(O(1)\) time.

---

Complexity

Time Complexity

• Number of states: \(O(N^2)\)
• Scanning transitions: The number of backward transitions from each state \((u, v, t)\) depends on the in-degree of the graph.
  • When \(t = 0\), the number of backward transitions for Aoki is \(\text{in-degree}(v) + 1\). Summing over all \(u, v\) gives \(\sum_{u=1}^N \sum_{v=1}^N (\text{in-degree}(v) + 1) = O(N(N + M))\).
  • When \(t = 1\), similarly, the total number of backward transitions for Takahashi is \(O(N(N + M))\).
• Query processing: \(O(1)\) for each of \(Q\) queries.

Therefore, the overall time complexity is \(O(N^2 + NM + Q)\). Under the constraints \(N \le 500, M \le N(N-1)\), the worst case involves approximately \(1.25 \times 10^8\) very simple loop operations, which comfortably fits within the time limit.

Space Complexity

• The win array for recording states and the deg array for recording degrees have size \(O(N^2)\).
• The adjacency lists G and revG for the graph have size \(O(N + M)\).

Therefore, the overall space complexity is \(O(N^2 + M)\). When \(N = 500\), the required memory is on the order of a few megabytes, making it very lightweight in terms of space.

---

Implementation Notes

• State Encoding (Optimization) The three-dimensional state \((u, v, t)\) is encoded into a single integer for queue management. $\(\text{code} = (u \times 505 + v) \times 2 + t\)$ This saves memory compared to using std::pair or structs, improves cache efficiency, and significantly increases execution speed.

• Fast I/O Since the number of queries \(Q\) can be up to \(100,000\), we use cin.tie(nullptr) and ios_base::sync_with_stdio(false), and use \n instead of std::endl for newlines, eliminating I/O bottlenecks.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> G[505];
vector<int> revG[505];

bool win[505][505][2];
int deg[505][505];
int q[600005];
int head = 0, tail = 0;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> N >> M)) return 0;

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        revG[v].push_back(u);
    }

    // Initialize degrees for Takahashi's turns.
    // Takahashi can either move to an adjacent room or stay in the current room.
    for (int u = 1; u <= N; ++u) {
        int d = 1 + G[u].size();
        for (int v = 1; v <= N; ++v) {
            deg[u][v] = d;
        }
    }

    // Base cases: u == v is an immediate win for Aoki (the chaser)
    for (int i = 1; i <= N; ++i) {
        win[i][i][0] = true;
        win[i][i][1] = true;
        q[tail++] = (i * 505 + i) * 2 + 0;
        q[tail++] = (i * 505 + i) * 2 + 1;
    }

    // BFS-like Backward Induction
    while (head < tail) {
        int curr = q[head++];
        int t = curr & 1;
        int tmp = curr >> 1;
        int v = tmp % 505;
        int u = tmp / 505;

        if (t == 0) {
            // Current state: (u, v, 0) is "Aoki wins"
            // Predecessors are Aoki's turn: (u, v_prev, 1) where v_prev can transition to v
            
            // Case 1: Aoki stays in the same room (v_prev = v)
            if (!win[u][v][1]) {
                win[u][v][1] = true;
                q[tail++] = (u * 505 + v) * 2 + 1;
            }
            // Case 2: Aoki moves from v_prev to v
            for (int v_prev : revG[v]) {
                if (!win[u][v_prev][1]) {
                    win[u][v_prev][1] = true;
                    q[tail++] = (u * 505 + v_prev) * 2 + 1;
                }
            }
        } else {
            // Current state: (u, v, 1) is "Aoki wins"
            // Predecessors are Takahashi's turn: (u_prev, v, 0) where u_prev can transition to u
            
            // Case 1: Takahashi stays in the same room (u_prev = u)
            if (!win[u][v][0]) {
                if (--deg[u][v] == 0) {
                    win[u][v][0] = true;
                    q[tail++] = (u * 505 + v) * 2 + 0;
                }
            }
            // Case 2: Takahashi moves from u_prev to u
            for (int u_prev : revG[u]) {
                if (!win[u_prev][v][0]) {
                    if (--deg[u_prev][v] == 0) {
                        win[u_prev][v][0] = true;
                        q[tail++] = (u_prev * 505 + v) * 2 + 0;
                    }
                }
            }
        }
    }

    // Answer each query in O(1)
    int Q;
    if (cin >> Q) {
        while (Q--) {
            int s, r;
            cin >> s >> r;
            if (win[s][r][0]) {
                cout << "NO\n";
            } else {
                cout << "YES\n";
            }
        }
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.