class Solution {
public:
    //space Complexity - O(1) If we are considering the recursion stack as the space complexity as well
    //then use SC - O(N) when the tree is left/right skewed
    //time Complexity - O(N), N is the number of nodes
    TreeNode* helper(int target, TreeNode *root) {
        if (root == nullptr)  return nullptr;
        root->left = helper(target, root->left);
        root->right = helper(target, root->right);
        //current node is the leaf node
        //we can delete this node
        if (root->left == nullptr && root->right == nullptr) {
            if (root->val == target) {
                return nullptr;
            } else {
                return root;
            }
        }
        return root;
    }
    
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        /// L, R, N
        if (root == nullptr) return nullptr;
        return helper(target, root);
        
    }
};

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        //red = [[0,1],[1,2]], blue = [[0,1],[1,2]]
        vector< pair<int, int> > graph[n + 1];
        //for red color - 0
        //for blue color - 1
        for (auto edge: red_edges) {
            graph[edge[0]].push_back({edge[1], 0});
        }
        
        for (auto edge: blue_edges) {
            // cout << edge[0] << " " << edge[1] << endl;
            graph[edge[0]].push_back({edge[1], 1});
        }
        
        //0 - 1
        
        //Space Complexity - O(2 * E) = max(O(E), O(V))
        //Time Complexity - O(2 * V) = O(V)
        
        
        queue< pair<int, int> > Q;
        int vis[n][2];
        vector<int> dis(n, -1);
        //init the vis matrix to identify If the color and the node combination has been visited or not
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 2; ++j) vis[i][j] = 0;
        }
        //Since this node 0 was not visited by any color of edge
        // Q.push({0, 0});
        Q.push({0, -1});
        vis[0][0] = 0;
        vis[0][1] = 0;
        int curIteration = 0;
        while(Q.size() > 0) {
            int curSize = Q.size();
            while(curSize--) {
                auto node = Q.front();
                Q.pop();
                if(dis[node.first] == -1) {
                    dis[node.first] = curIteration;
                }
                //go to all the adjacent nodes and try to push them into the queue
                for (auto destination: graph[node.first]) {
                    if(node.second != destination.second && vis[destination.first][destination.second] == 0) {
                        Q.push({destination.first, destination.second});
                        vis[destination.first][destination.second] = 1;
                    }
                }
//                 //meaning that we have not visited this node yet
//                 if (dis[node.first] == -1) {
                    
//                 } 
            }
            ++curIteration;
        }
        return dis;
    }
};