<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>> find_parents(vector<int> node, vector<vector<int>>& graph)
    {
        vector<vector<int>> parents;
        int t_node = node[2], m_node = node[0], c_node = node[1];
        if(t_node ==0) // turn of node is 0 that is a Mouse node
        {
            for(auto& v : graph[c_node])
            {
                if(v != 0) // cat is not allowed to visit Hole
                {
                    vector<int> temp = {m_node, v, 1};
                    parents.push_back(temp);
                }
            }
        }
        else if(t_node ==1) // turn of node is 1 that is a cat node
        {
            for(auto& v : graph[m_node])
            {
                vector<int> temp = {v, c_node, 0};
                parents.push_back(temp);
            }
        }
        return parents;
    }
    int catMouseGame(vector<vector<int>>& graph) {
                ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        int n = graph.size();
        vector<vector<vector<int>>> result;
        vector<int> temp_1d(2, 0);
        vector<vector<int>> temp_2d(n, temp_1d);
        for(int i = 0 ; i < n;i++)
        {
            result.push_back(temp_2d);
        }
        vector<vector<vector<int>>> degree = result; // degree 3d matrix will store how many DRAW children does state [m][c][t] have
        for(int i = 1; i < n; i++)
        {
            result[0][i][0] = 1; // 1 will refer to Mouse Win
            result[0][i][1] = 1;
            result[i][i][0] = 2; // 2 will refer to Cat Win also 0 will refer to DRAW
            result[i][i][1] = 2; 
        }
        for(int i = 1 ; i < n; i++)
        {
            for(int j = 1; j < n ; j++)
            {
                degree[i][j][0] = int(graph[i].size()); // if it is a mouse turn then if children come out to be Cat Win states then I can check atmost for graph[i].size() many children
                degree[i][j][1] = int(graph[j].size()); // if it is a cat turn and if children come out to be Mouse Win states then I can check for atmost graph[j].size() many children
            }
        // We need not worry 
        }
        for(auto& j : graph[0])
        {
            for(int i = 1; i < n ; i++)
            {
                degree[i][j][1]--; // if it is cat Turn then we do not want child nodes where cat moves to Hole
            }
        }
        queue<vector<int>> q;
        vector<int> temp1;
        vector<int> temp2;
        vector<int> temp3;
        vector<int> temp4;
        for(int i = 1 ; i < n; i++)
        {
            temp1 = {0, i, 0};
            temp2 = {0, i, 1};
            temp3 = {i, i, 0};
            temp4 = {i, i, 1};
            q.push(temp1);
            q.push(temp2);
            q.push(temp3);
            q.push(temp4);
        }

        while(q.empty() != 1)
        {
            vector<int> head = q.front();
            q.pop();
            int m_head = head[0], c_head = head[1], t_head = head[2];
            vector<vector<int>> parents = find_parents(head, graph);
            int m_parent, c_parent, t_parent;
            for(auto& parent: parents)
            {
                m_parent = parent[0], c_parent = parent[1], t_parent = parent[2];
                int initial_result = result[m_parent][c_parent][t_parent];
                if(result[m_parent][c_parent][t_parent] != 0 )
                {
                    continue;
                }
                if(t_parent == 0 ) // parent turn is Mouse
                {
                    if(result[m_head][c_head][t_head] == 1) // if result of chlild node is a Mouse Win 
                    {
                        result[m_parent][c_parent][t_parent] = 1; // immediatedly assign the state Mouse Win
                    }
                    else  // if result of child node is Cat Win
                    {
                        degree[m_parent][c_parent][t_parent]--;
                        if(degree[m_parent][c_parent][t_parent] == 0)
                        {
                            result[m_parent][c_parent][t_parent] = 2; // if all child nodes are Cat  Wins then this node will also be a Cat win
                        }
                    }
                }
                if(t_parent == 1 ) // parent turn is Cat
                {
                    if(result[m_head][c_head][t_head] == 2) // if result of chlild node is a Cat Win 
                    {
                        result[m_parent][c_parent][t_parent] = 2; // immediatedly assign the state Cat Win
                    }
                    else // if result of child node is Mouse Win
                    {
                        degree[m_parent][c_parent][t_parent]--;
                        if(degree[m_parent][c_parent][t_parent] == 0)
                        {
                            result[m_parent][c_parent][t_parent] = 1; // if all child nodes are Mouse Wins then this node will also be a Mouse win
                        }
                    }
                }
                int final_result = result[m_parent][c_parent][t_parent];
                if(initial_result != final_result)
                {
                    q.push(parent);
                }
            }
        }
        return result[1][2][0];


    }
};
            //         for(int i1 = 0 ; i1 < result.size(); i1++)
            // {
            //     for(int i2 = 1 ; i2 < result[0].size(); i2++)
            //     {
            //         for(int i3 = 0 ; i3 < result[0][0].size(); i3++)
            //         {
            //             cout<< '('<<i1<<','<<i2<<','<<i3<<')'<<"-> "<< result[i1][i2][i3]<<' ';
            //         }
            //         cout<<'\n';
            //     }
            //     cout<<"\n\n-----------------\n\n";
            // }
188775