<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>

#define PRINT false
#if PRINT
    string __DBG; void clearDebug() { __DBG = "\n"; } void debugPrint() { throw runtime_error(__DBG); }
    #define print(...) __DBG += format(__VA_ARGS__)
    #define println(...) print(__VA_ARGS__); __DBG.push_back('\n')
    #define panic(...) println(__VA_ARGS__); debugPrint()
#else
    void clearDebug() {} void debugPrint() {}
    #define print(...)
    #define println(...)
    #define panic(...) abort()
#endif

enum Result: int8_t {
    Unknown = -1,
    Draw = 0,
    Mouse = 1,
    Cat = 2,
};
constexpr const char* resultName(Result r) {
    switch (r) {
        case Unknown: return "Unknown";
        case Draw: return "Draw";
        case Mouse: return "Mouse";
        case Cat: return "Cat";
        default: return "INVALID";
    }
}

struct State {
    uint8_t cat, mouse;
    bool catMoved;
};

array<array<array<uint8_t, 2>, 51>, 51> numEdges; // cat => mouse => catMoved => num incoming edges
array<array<array<Result, 2>, 51>, 51> result; // cat => mouse => catMoved => result
class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        clearDebug();

        if (graph[1].size() == 1 && graph[1][0] == 2) {
            return Cat; // Mouse has to move onto cat
        }

        const int n = graph.size();
        queue<State> frontier;
        for (int cat = 1; cat < n; ++cat) {
            result[cat][0] = {Mouse, Mouse};
            numEdges[cat][0] = {0, 0};
            frontier.emplace(cat, 0, false);
            frontier.emplace(cat, 0, true);
            for (int mouse = 1; mouse < n; ++mouse) {
                if (cat == mouse) {
                    result[cat][mouse] = {Cat, Cat};
                    numEdges[cat][mouse] = {0, 0};
                    frontier.emplace(cat, mouse, false);
                    frontier.emplace(cat, mouse, true);
                } else {
                    result[cat][mouse] = {Unknown, Unknown};
                }
                numEdges[cat][mouse] = {
                    (uint8_t)(graph[cat].size() - (ranges::find(graph[cat], 0) != graph[cat].end())),
                    (uint8_t)graph[mouse].size(),
                };
            }
        }

        while (!frontier.empty()) {
            auto [cat, mouse, catMoved] = frontier.front();
            frontier.pop();
            auto current = result[cat][mouse][catMoved];
            println("Processing {},{}:{} -> {}", cat, mouse, catMoved ? "Cat" : "Mouse", resultName(current));
            if (catMoved) {
                for (int prevCat : graph[cat]) {
                    if (prevCat == 0) { continue; }
                    Result& prev = result[prevCat][mouse][!catMoved];
                    auto& prevEdges = numEdges[prevCat][mouse][!catMoved];
                    if (prev != Unknown) { continue; }
                    if (--prevEdges == 0 || current == Cat) {
                        println("  Setting {},{}:{} to {}", prevCat, mouse, !catMoved ? "Cat" : "Mouse", resultName(current));
                        prev = current;
                        frontier.emplace(prevCat, mouse, !catMoved);
                    } else {
                        println("    dec {},{}:{} -> {}", prevCat, mouse, !catMoved ? "Cat" : "Mouse", prevEdges);
                    }
                }
            } else {
                for (int prevMouse : graph[mouse]) {
                    Result& prev = result[cat][prevMouse][!catMoved];
                    auto& prevEdges = numEdges[cat][prevMouse][!catMoved];
                    if (prev != Unknown) { continue; }
                    if (--prevEdges == 0 || current == Mouse) {
                        println("  Setting {},{}:{} to {}", cat, prevMouse, !catMoved ? "Cat" : "Mouse", resultName(current));
                        prev = current;
                        if (prevMouse == 1 && cat == 2) {
                            println("Finished");
                            debugPrint();
                            return current;
                        }
                        frontier.emplace(cat, prevMouse, !catMoved);
                    } else {
                        println("    dec {},{}:{} -> {}", cat, prevMouse, !catMoved ? "Cat" : "Mouse", prevEdges);
                    }
                }
            }
        }
        println("Draw");
        debugPrint();
        return Draw;
    }
};

/*

[[2,3],[2],[0,1],[0,4],[3]]

0---2---1
|       
3---4

*/
14475