<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:
        n=len(graph)
        states=[[[0]*2 for _ in range(n)] for _ in range(n)] # states[i][j][k] - cat at i, mouse at j
        # k=0, mouse's turn, k=1, cat' turn
        # states value: -1 not reachable, 1, mouse win, 2 cat win, 0 draw
        for i in range(n):
            states[0][i][0]=-1  # cat cannot get to node 0
            states[0][i][1]=-1  # cat cannot get to node 0
        for i in range(1, n):
            states[i][0][1]=1 # when mouse gets node 0, mouse win
            states[i][0][0]=-1
            states[i][i][0]=2 # when cat and mouse are at same node, cat win
            states[i][i][1]=2 # when cat and mouse are at same node, cat win
        while True: # bellman -ford loop n-1 times
            isUpdating=False
            for i in range(1, n):
                for j in range(n):
                    for k in range(2):
                        if states[i][j][k]!=0:
                            continue
                        if k==0:
                            value=2
                            # mouse's turn, if any adjacent value of j states[i][u][0] mouse win, then mouse win
                            # if any adjacent value draw, and no adj mouse win, then a draw
                            for u in graph[j]:
                                if states[i][u][1]==1:
                                    value=1
                                    break
                                if states[i][u][1]==0:
                                    value=0
                            if value!=0:
                                isUpdating=True
                            states[i][j][k]=value
                        else: # cat's turn
                            value=1
                            # if for any adjacent, cat win, then cat win
                            # if for any adjacet it'a draw, and cat cannot win anywhere then it's draw
                            for u in graph[i]:
                                if states[u][j][0]==2:
                                    value=2
                                    break
                                if states[u][j][0]==0:
                                    value=0
                            if value!=0:
                                isUpdating=True
                            states[i][j][k]=value
            if not isUpdating or states[2][1][0]!=0:
                return states[2][1][0]
        
16700