<p>A game on an <strong>undirected</strong> graph is played by two players, Mouse and Cat, who alternate turns.</p>

<p>The graph is given as follows: <code>graph[a]</code> is a list of all nodes <code>b</code> such that <code>ab</code> is an edge of the graph.</p>

<p>The mouse starts at node <code>1</code> and goes first, the cat starts at node <code>2</code> and goes second, and there is a hole at node <code>0</code>.</p>

<p>During each player&#39;s turn, they <strong>must</strong> travel along one&nbsp;edge of the graph that meets where they are.&nbsp; For example, if the Mouse is at node 1, it <strong>must</strong> travel to any node in <code>graph[1]</code>.</p>

<p>Additionally, it is not allowed for the Cat to travel to the Hole (node <code>0</code>).</p>

<p>Then, the game can end in three&nbsp;ways:</p>

<ul>
	<li>If ever the Cat occupies the same node as the Mouse, the Cat wins.</li>
	<li>If ever the Mouse reaches the Hole, the Mouse wins.</li>
	<li>If ever a position is repeated (i.e., the players are in the same position as a previous turn, and&nbsp;it is the same player&#39;s turn to move), the game is a draw.</li>
</ul>

<p>Given a <code>graph</code>, and assuming both players play optimally, return</p>

<ul>
	<li><code>1</code>&nbsp;if the mouse wins the game,</li>
	<li><code>2</code>&nbsp;if the cat wins the game, or</li>
	<li><code>0</code>&nbsp;if the game is a draw.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/17/cat1.jpg" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/17/cat2.jpg" style="width: 200px; height: 200px;" />
<pre>
<strong>Input:</strong> graph = [[1,3],[0],[3],[0,2]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= graph.length &lt;= 50</code></li>
	<li><code>1&nbsp;&lt;= graph[i].length &lt; graph.length</code></li>
	<li><code>0 &lt;= graph[i][j] &lt; graph.length</code></li>
	<li><code>graph[i][j] != i</code></li>
	<li><code>graph[i]</code> is unique.</li>
	<li>The mouse and the cat can always move.&nbsp;</li>
</ul>

enum class State { kDraw, kMouseWin, kCatWin };

class Solution {
 public:
  int catMouseGame(vector<vector<int>>& graph) {
    const int n = graph.size();
    // result of (cat, mouse, move)
    // move := 0 (mouse) / 1 (cat)
    vector<vector<vector<State>>> states(
        n, vector<vector<State>>(n, vector<State>(2)));
    vector<vector<vector<int>>> outDegree(
        n, vector<vector<int>>(n, vector<int>(2)));
    queue<tuple<int, int, int, State>> q;  // (cat, mouse, move, state)

    for (int cat = 0; cat < n; ++cat)
      for (int mouse = 0; mouse < n; ++mouse) {
        outDegree[cat][mouse][0] = graph[mouse].size();
        outDegree[cat][mouse][1] =
            graph[cat].size() - ranges::count(graph[cat], 0);
      }

    // Start from the states s.t. the winner can be determined.
    for (int cat = 1; cat < n; ++cat)
      for (int move = 0; move < 2; ++move) {
        // Mouse is in the hole.
        states[cat][0][move] = State::kMouseWin;
        q.emplace(cat, 0, move, State::kMouseWin);
        // Cat catches mouse.
        states[cat][cat][move] = State::kCatWin;
        q.emplace(cat, cat, move, State::kCatWin);
      }

    while (!q.empty()) {
      const auto [cat, mouse, move, state] = q.front();
      q.pop();
      if (cat == 2 && mouse == 1 && move == 0)
        return static_cast<int>(state);
      const int prevMove = move ^ 1;
      for (const int prev : graph[prevMove ? cat : mouse]) {
        const int prevCat = prevMove ? prev : cat;
        if (prevCat == 0)  // invalid
          continue;
        const int prevMouse = prevMove ? mouse : prev;
        // The state has been determined.
        if (states[prevCat][prevMouse][prevMove] != State::kDraw)
          continue;
        if (prevMove == 0 && state == State::kMouseWin ||
            prevMove == 1 && state == State::kCatWin ||
            --outDegree[prevCat][prevMouse][prevMove] == 0) {
          states[prevCat][prevMouse][prevMove] = state;
          q.emplace(prevCat, prevMouse, prevMove, state);
        }
      }
    }

    return static_cast<int>(states[2][1][0]);
  }
};
26925