<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:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        mouse = 0
        cat = 1
        mouse_win = 1
        cat_win = 2
        draw = 0
        n = len(graph)
        result = {}
        for i in range(1, n):
            result[(0, i, cat)] = result[(0, i, mouse)] = mouse_win
            result[(i, i, cat)] = result[(i, i, mouse)] = cat_win
        degree = {}
        for curr_mouse in range(1, n):
            for curr_cat in range(1, n):
                degree[(curr_mouse, curr_cat, mouse)] = len(graph[curr_mouse])
                degree[(curr_mouse, curr_cat, cat)] = len(graph[curr_cat])-int(0 in graph[curr_cat])
        queue = deque([state for state in result.keys()])
        while queue:
            curr_mouse, curr_cat, curr_turn = queue.popleft()
            curr_result = result[(curr_mouse, curr_cat, curr_turn)]
            prev_states = []
            if curr_turn == mouse:
                prev_states = [(curr_mouse, prev_cat, cat) for prev_cat in graph[curr_cat]]
            else:
                prev_states = [(prev_mouse, curr_cat, mouse) for prev_mouse in graph[curr_mouse]]
            for prev_state in prev_states:
                if prev_state in result:
                    continue
                prev_mouse, prev_cat, prev_turn = prev_state
                if prev_cat == 0:
                    continue
                degree[prev_state] -= 1
                mover_win = (curr_result == mouse_win and prev_turn == mouse) or (curr_result == cat_win and prev_turn == cat)
                if mover_win or degree[prev_state] == 0:
                    result[prev_state] = curr_result
                    queue.append(prev_state)
        if (1, 2, mouse) in result:
            return result[(1, 2, mouse)]
        else:
            return draw


        # # not working on some testcases
        # n = len(graph)
        # memory = {}
        # def dfs(curr_mouse, curr_cat, curr_turn):
        #     if (curr_mouse, curr_cat, curr_turn) in memory:
        #         return memory[(curr_mouse, curr_cat, curr_turn)]
        #     if curr_mouse == 0:
        #         return 1
        #     if curr_mouse == curr_cat:
        #         return 2
        #     if curr_turn >= 2*n:
        #         return 0
        #     if curr_turn%2 == 0:
        #         next_nodes = graph[curr_mouse]
        #         result = 2
        #         for next_node in next_nodes:
        #             next_result = dfs(next_node, curr_cat, curr_turn+1)
        #             if next_result == 1:
        #                 result = 1
        #                 break
        #             elif next_result == 0:
        #                 result = 0
        #     else:
        #         next_nodes = graph[curr_cat]
        #         result = 1
        #         for next_node in next_nodes:
        #             if next_node == 0:
        #                 continue
        #             next_result = dfs(curr_mouse, next_node, curr_turn+1)
        #             if next_result == 2:
        #                 result = 2
        #                 break
        #             elif next_result == 0:
        #                 result = 0
        #     memory[(curr_mouse, curr_cat, curr_turn)] = result
        #     return result
        # return dfs(1, 2, 0)

17600