A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.

The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.

The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0.

During each player's turn, they must travel along one&nbsp;edge of the graph that meets where they are.&nbsp; For example, if the Mouse is at node 1, it must travel to any node in graph[1].

Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)

Then, the game can end in three&nbsp;ways:


	If ever the Cat occupies the same node as the Mouse, the Cat wins.
	If ever the Mouse reaches the Hole, the Mouse wins.
	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's turn to move), the game is a draw.


Given a graph, and assuming both players play optimally, return


	1&nbsp;if the mouse wins the game,
	2&nbsp;if the cat wins the game, or
	0&nbsp;if the game is a draw.


&nbsp;
Example 1:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0


Example 2:

Input: graph = [[1,3],[0],[3],[0,2]]
Output: 1


&nbsp;
Constraints:


	3 &lt;= graph.length &lt;= 50
	1&nbsp;&lt;= graph[i].length &lt; graph.length
	0 &lt;= graph[i][j] &lt; graph.length
	graph[i][j] != i
	graph[i] is unique.
	The mouse and the cat can always move.&nbsp;


class Solution:
    def catMouseGame(self, graph: List[List[int]]) -> int:
        def getPreStates(m,c,t):
            ans = []
            if t == 1:
                for c2 in graph[c]:
                    if c2 == 0:continue
                    ans.append((m,c2,2))
            else:
                for m2 in graph[m]:
                    ans.append((m2,c,1))
            return ans
        
        def ifAllNextMovesFailed(m,c,t):
            if t == 1:
                for m2 in graph[m]:
                    if result[(m2,c,2)] != 2:return False
            else:
                for c2 in graph[c]:
                    if c2 == 0:continue
                    if result[(m,c2,1)] != 1:return False
            return True
        
        result = defaultdict(lambda:0) 
        # key = (m,c,turn) value = (0/1/2)
        n = len(graph)
        queue = deque()
        
        for t in range(1,3):
            for i in range(1,n):
                # mouse win 
                result[(0,i,t)] = 1
                queue.append((0,i,t))
                # cat win
                result[(i,i,t)] = 2
                queue.append((i,i,t))
        
        while queue:
            m,c,t = queue.popleft()
            r = result[(m,c,t)]
            for m2,c2,t2 in getPreStates(m,c,t):
                r2 = result[(m2,c2,t2)]
                if r2 > 0:continue
                # populate prestate
                if r == 3-t: # can always win
                    result[(m2,c2,t2)] = r
                    queue.append((m2,c2,t2))
                elif ifAllNextMovesFailed(m2,c2,t2):
                    result[(m2,c2,t2)] =3-t2
                    queue.append((m2,c2,t2))
        return result[(1,2,1)]
                    
class Solution {
    int TIME_MAX = 200;
    int DRAW = 0;
    int MOUSE_WIN = 1;
    int CAT_WIN = 2;
    public int catMouseGame(int[][] graph) {
        return dfs(0, new int[]{1, 2}, graph, new Integer[TIME_MAX+1][graph.length][graph.length]);
    }

    private int dfs(int time, int[] p, int[][] graph, Integer[][][] memo){ // p[0] -> mouse position, p[1] -> cat position
        Integer old = memo[time][p[0]][p[1]];
        if (old != null) return old; // all the base cases here
        if (time >= TIME_MAX) return DRAW;
        if (p[0]==0) return MOUSE_WIN;
        if (p[0]==p[1]) return CAT_WIN;
        int state = 0;
        int where = p[time&1];
        int res = DRAW;
        for (int i = 0; i < graph[where].length; i++){
            if ((time&1)==0||graph[where][i]>0){ // if mouse turn or cat turn and the dest is not 0, do ...
                p[time&1]=graph[where][i];
                state |= 1 << dfs(time+1, p, graph, memo);
                if ((time&1)>0&&(state&4)>0 || (time&1)==0&&(state&2)>0) // if mouse's turn & mouse win
                    break; // or cat's turn & cat win, then we stop.
            }
        }
        p[time&1]=where; // restore p
        if (((time&1)>0 && (state & 4)>0)||((time&1)==0) && state==4){
            res = CAT_WIN; // cat win when (cat's turn & cat win) or (mouse's turn and state = cat)
        }else if (((time&1)==0 && (state & 2)>0)||(time&1)==1 && state==2){
            res = MOUSE_WIN; // mouse win when (mouse's turn and mouse win) or (cat's turn and state = mouse)
        }
        return memo[time][p[0]][p[1]]=res;
    }
}
class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        int N = graph.size();
        vector<vector<int>> dp[2];
        vector<vector<int>> outdegree[2];
        queue<vector<int>> q; // q of {turn, mouse position, cat position} for topological sort

        dp[0] = vector<vector<int>>(N, vector<int>(N));
        dp[1] = vector<vector<int>>(N, vector<int>(N));
        outdegree[0] = vector<vector<int>>(N, vector<int>(N));
        outdegree[1] = vector<vector<int>>(N, vector<int>(N));

        // init dp and queue
        for (int j = 0; j < N; ++j) {
            dp[0][0][j] = dp[1][0][j] = 1;
            q.push({0, 0, j});
            q.push({1, 0, j});
        }
        for (int j = 1; j < N; ++j) {
            dp[0][j][j] = dp[1][j][j] = 2;
            q.push({0, j, j});
            q.push({1, j, j});
        }
        // init outdegree
        for (int i = 0; i < N; ++i) {
            for (int j = 1; j < N; ++j) {
                outdegree[0][i][j] = graph[i].size();
                outdegree[1][i][j] = graph[j].size();
            }
        }
        for (auto &v : graph[0]) {
            for (int i = 0; i < N; ++i) {
                outdegree[1][i][v]--;
            }
        }
        // run the topological sort from queue
        while (q.size()) {
            auto turn = q.front()[0];
            auto mouse = q.front()[1];
            auto cat = q.front()[2];
            q.pop();

            if (turn == 0 && mouse == 1 && cat == 2) {
                // the result has been inferenced
                break;
            }

            if (turn == 0) { // mouse's turn
                // v is the prev position of cat
                for (auto &v : graph[cat]) {
                    if (v == 0) {
                        continue;
                    }

                    if (dp[1][mouse][v] > 0) {
                        continue;
                    }

                    if (dp[turn][mouse][cat] == 2) {
                        // cat wants to move from v to `cat` position, and thus cat wins
                        dp[1][mouse][v] = 2;
                        q.push({1, mouse, v});
                        continue;
                    }

                    outdegree[1][mouse][v]--;
                    if (outdegree[1][mouse][v] == 0) {
                        dp[1][mouse][v] = 1;
                        q.push({1, mouse, v});
                    }
                }
            } else { // cat's turn
                // v is the prev position of mouse
                for (auto &v : graph[mouse]) {
                    if (dp[0][v][cat] > 0) {
                        continue;
                    }

                    if (dp[turn][mouse][cat] == 1) {
                        // mouse wants to move from v to `mouse` position and thus mouse wins
                        dp[0][v][cat] = 1;
                        q.push({0, v, cat});
                        continue;
                    }

                    outdegree[0][v][cat]--;
                    if (outdegree[0][v][cat] == 0) {
                        dp[0][v][cat] = 2;
                        q.push({0, v, cat});
                    }
                }
            }
        }

        return dp[0][1][2];
    }
};
var catMouseGame = function(graph) {
    let n=graph.length,
        memo=[...Array(n+1)].map(d=>[...Array(n+1)].map(d=>[...Array(2*n+1)])),
        seen=[...Array(n+1)].map(d=>[...Array(n+1)].map(d=>[...Array(2)]))
    //dfs returns 0 1 2, whether the current player loses,wins, or draws respectively
    let dfs=(M,C,level)=>{
        let turn=level%2,curr=turn?C:M,draw=0,res=0
        //draw when we ve seen the state before or cycles
        if(seen[M][C][turn]!==undefined||level>=2*n) 
            return memo[M][C][level]=2 
        if(M==0)// win for mouse if it reaches the hole, loss for cat
            memo[M][C][level]=turn^1
        if(M==C)// win for cat if it reaches the mouse, loss for mouse
            memo[M][C][level]=turn 
        if(memo[M][C][level]===undefined){
            seen[M][C][turn]=0 //set this state as visited
            for(let i=0;i<graph[curr].length&&!res;i++) //traverse for the available edges
                if( !(turn&&(!graph[curr][i]))){ //The cat cant move into the hole
                    let val=turn?
                            dfs(M,graph[curr][i],level+1):
                            dfs(graph[curr][i],C,level+1)
                    if(val===2) 
                        draw=1 //set draw as an available option
                    else
                        res|=(1^val) //minimax logic, always prefer the losing state of the opponent
                }
            memo[M][C][level]=res||(2*draw) // set in this order 1->2->0 
        }
        seen[M][C][turn]=undefined;// de-set the state for the current game,as it concluded
        return memo[M][C][level]
    }
    return [2,1,0][dfs(1,2,0)] //js eye candy
};
Cat and Mouse