<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 {
public:

    vector<vector<int>>adj;
    set<pair<pair<int,int>,int>>st;
    int dp[51][51][2];

    int solve(int i, int j, int k,int win){
       if(i==j){
        return 2;
       }
       else if(i==0){
        return 1;
       }
        if(dp[i][j][k]!=-1 ){
            return dp[i][j][k];
        }
        if(st.find({{i,j},k})!=st.end()){
            return 0;
        }
        else{
            st.insert({{i,j},k});
        }
        bool won=false;
        bool draw=false;
 
        if(k==0){
            int temp;
            for(auto it:adj[i]){
               temp=solve(it,j,1,2);
               if(temp==0){
                draw=true;
               }
               else if(temp==1){
                won=true;
                break;
               }
            }
            
        }
        else{
            int temp;
            for(auto it:adj[j]){
                if(it==0){
                    continue;
                }
                temp=solve(i,it,0,1);
             
                if(temp==0){
                 draw=true;
                }
                else if(temp==2){
                won=true;
                break;
                }
            }
        }
        st.erase({{i,j},k});
        if(won){
            return dp[i][j][k]=win;
        }
        else if(draw){
            return dp[i][j][k]= 0;
        }
        else {
            if(win==1){
                return dp[i][j][k]=2;
            }
            else{
                return dp[i][j][k]=1;
            }
        }
    }


    int catMouseGame(vector<vector<int>>& graph) {
        adj=graph;
        int ans;
        for(int turn=0;turn<50;turn++){
           for(int i=0;i<51;i++){
            for(int j=1;j<51;j++){
                for(int k=0;k<2;k++){
                if(dp[i][j][k]==0){
                    dp[i][j][k]=-1;
                }
                }
            }
        }
        ans=solve(1,2,0,1);
        }
        return ans;
    }
};
55975