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

class Solution {
private:
    const int MOUSE_WIN = 1, CAT_WIN = 2, DRAW = 0, CAT_TURN = 2, MOUSE_TURN = 1;
    void setChildrenCatAndMouse(int n, vector<vector<vector<int>>> &num_children, vector<vector<int>>& adj) {
        for(int m = 0; m < n; m++) {
            for(int c = 0; c < n; c++) {
                num_children[m][c][MOUSE_TURN] = adj[m].size();
                num_children[m][c][CAT_TURN] = adj[c].size();
                for(int x : adj[c]) {
                    if(!x) {
                        num_children[m][c][CAT_TURN]--;
                        break;
                    }
                }
            }
        }
    }

    vector<vector<int>> getParents(vector<vector<int>>& adj, int m, int c, int t) {
        vector<vector<int>> ans;
        if(t == CAT_TURN) {
            for(auto m2 : adj[m]) {
                ans.push_back({m2, c, MOUSE_TURN});
            }
        } else {
            for(auto c2 : adj[c]) {
                if(c2) {
                    ans.push_back({m, c2, CAT_TURN});
                }
            }
        }
        return ans;
    }
public:
    int catMouseGame(vector<vector<int>>& adj) {
        int n = adj.size();
        vector<vector<vector<int>>> color(n, vector<vector<int>>(n, vector<int>(3, 0)));
        // [mouse_loc][cat_loc][whose_turn]
        vector<vector<vector<int>>> children_num(n, vector<vector<int>>(n, vector<int>(3, 0)));
        setChildrenCatAndMouse(n, children_num, adj);
        queue<vector<int>> q;
        for(int i=0;i<n;i++) {
            for(int t=1; t<=2; t++) {
                color[0][i][t] = MOUSE_WIN;
                q.push({0, i, t, MOUSE_WIN});
                if(i) {
                    color[i][i][t] = CAT_WIN;
                    q.push({i, i, t, CAT_WIN});
                }
            }
        }
        while(!q.empty()) {
            auto it = q.front();
            q.pop();
            int m = it[0], c = it[1], t = it[2], col = it[3];
            for(auto parent : getParents(adj, m, c, t)) {
                int m2 = parent[0], c2 = parent[1], t2 = parent[2];
                if(color[m2][c2][t2] == DRAW) {
                    if((t2 == MOUSE_TURN && col == MOUSE_WIN) ||(t2 == CAT_TURN && col == CAT_WIN)) {
                        color[m2][c2][t2] = col;
                        q.push({m2, c2, t2, col});
                    } else {
                        children_num[m2][c2][t2]--;
                        if(!children_num[m2][c2][t2]) {
                            color[m2][c2][t2] = t2 == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
                            q.push({m2, c2, t2, color[m2][c2][t2]});
                        }
                    }
                }
            }
        }

        return color[1][2][MOUSE_TURN];
    }
};
180475