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

from collections import deque

class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:

        n = len(graph)
        
        # Define game states: 0 = draw, 1 = mouse wins, 2 = cat wins
        dp = [[[0] * 2 for _ in range(n)] for _ in range(n)]
        
        # degrees[i][j][0] means the number of unprocessed moves when it's mouse's turn
        # degrees[i][j][1] means the number of unprocessed moves when it's cat's turn
        degrees = [[[0] * 2 for _ in range(n)] for _ in range(n)]
        
        # Initialize queue for BFS
        queue = deque()
        
        # Initialize degrees and base cases
        for mouse in range(n):
            for cat in range(n):
                if mouse == 0:
                    dp[mouse][cat][0] = 1  # Mouse wins
                    dp[mouse][cat][1] = 1  # Mouse wins
                    queue.append((mouse, cat, 0, 1))
                    queue.append((mouse, cat, 1, 1))
                elif mouse == cat:
                    dp[mouse][cat][0] = 2  # Cat wins
                    dp[mouse][cat][1] = 2  # Cat wins
                    queue.append((mouse, cat, 0, 2))
                    queue.append((mouse, cat, 1, 2))
                else:
                    degrees[mouse][cat][0] = len(graph[mouse])  # Mouse's turn
                    degrees[mouse][cat][1] = len(graph[cat]) - (0 in graph[cat])  # Cat's turn, cat can't go to the hole
        
        # BFS propagation
        while queue:
            mouse, cat, turn, result = queue.popleft()
            
            # Turn 0 means it's the mouse's turn, Turn 1 means it's the cat's turn
            prev_turn = 1 - turn
            
            if turn == 0:  # Mouse's turn, propagate to cat's turn
                for prev_cat in graph[cat]:
                    if prev_cat == 0:  # Cat can't move to the hole
                        continue
                    if dp[mouse][prev_cat][prev_turn] == 0:
                        # If it's a loss for the current turn player, it's a win for the previous turn player
                        if result == 2:  # Cat wins in current state, propagate that it's a win for cat
                            dp[mouse][prev_cat][prev_turn] = 2
                            queue.append((mouse, prev_cat, prev_turn, 2))
                        else:
                            degrees[mouse][prev_cat][prev_turn] -= 1
                            if degrees[mouse][prev_cat][prev_turn] == 0:  # No more options, it's a loss for cat
                                dp[mouse][prev_cat][prev_turn] = 1
                                queue.append((mouse, prev_cat, prev_turn, 1))
            
            else:  # Cat's turn, propagate to mouse's turn
                for prev_mouse in graph[mouse]:
                    if dp[prev_mouse][cat][prev_turn] == 0:
                        # If it's a loss for the current turn player, it's a win for the previous turn player
                        if result == 1:  # Mouse wins in current state, propagate that it's a win for mouse
                            dp[prev_mouse][cat][prev_turn] = 1
                            queue.append((prev_mouse, cat, prev_turn, 1))
                        else:
                            degrees[prev_mouse][cat][prev_turn] -= 1
                            if degrees[prev_mouse][cat][prev_turn] == 0:  # No more options, it's a loss for mouse
                                dp[prev_mouse][cat][prev_turn] = 2
                                queue.append((prev_mouse, cat, prev_turn, 2))
        
        # The result for the initial state (mouse at 1, cat at 2, mouse's turn)
        return dp[1][2][0]



17500