You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:


	redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
	blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.


Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

&nbsp;
Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]


Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]


&nbsp;
Constraints:


	1 &lt;= n &lt;= 100
	0 &lt;= redEdges.length,&nbsp;blueEdges.length &lt;= 400
	redEdges[i].length == blueEdges[j].length == 2
	0 &lt;= ai, bi, uj, vj &lt; n


class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        g = [[[] for _ in range(2)] for _ in range(n)]
        
        for i,j in redEdges:
            g[i][0] += [j]
        for i,j in blueEdges:
            g[i][1] += [j]
        distance = [float("inf") for _ in range(n)]
        distance[0] = 0
        q = queue.Queue()
        q.put((0,0,False))
        q.put((0,0,True))
        
        redS = set([0])
        blueS = set([0])
        while not q.empty():
            node,dist,red = q.get()
            if red:
                neighbours = g[node][0]
                redS.add(node)
                curr = blueS
            else:
                neighbours = g[node][1]
                blueS.add(node)
                curr = redS
            for neighbour in neighbours:
                if dist + 1 < distance[neighbour]:
                    distance[neighbour] = dist + 1
                    q.put((neighbour,dist + 1,not red))
                if not (neighbour in curr):
                    q.put((neighbour,dist + 1,not red))
        for i in range(n):
            if distance[i] == float("inf"):
                distance[i] = -1
        return distance
            
class Solution {
    // g1-> graph with red edges
    // g2-> graph with blue edges
    List<Integer> g1[], g2[];
    int[] dist1, dist2, ans;
    int MX = (int) 2e9;

    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        dist1 = new int[n];
        dist2 = new int[n];
        g1=new ArrayList[n];
        g2=new ArrayList[n];
        ans=new int[n];
        for (int i=0;i<n;i++){
            g1[i]=new ArrayList<>();
            g2[i]=new ArrayList<>();
            dist1[i]=MX;
            dist2[i]=MX;
            ans[i]=MX;
        }
        for (int i=0;i<redEdges.length;i++){
            int u=redEdges[i][0];
            int v=redEdges[i][1];
            g1[u].add(v);
        }
        for (int i=0;i<blueEdges.length;i++){
            int u=blueEdges[i][0];
            int v=blueEdges[i][1];
            g2[u].add(v);
        }
        dist1[0]=0;
        dist2[0]=0;
        dfs(0,true);
        dfs(0,false);
        for (int i=0;i<n;i++){
            ans[i]=Math.min(dist1[i], dist2[i]);
            if (ans[i]==MX) ans[i]=-1;
        }
        return ans;
    }
    public void dfs(int u, boolean flag) {
        if (flag) {
            for (int v: g1[u]) {
                if (dist1[v]>dist2[u]+1){
                    dist1[v]=dist2[u]+1;
                    dfs(v,!flag);
                }
            }
        } else {
            for (int v: g2[u]) {
                if (dist2[v]>dist1[u]+1){
                    dist2[v]=dist1[u]+1;
                    dfs(v,!flag);
                }
            }
        }
    }
}
#define red 1
#define blue 2
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<pair<int,int>>> graph(n);
        vector<vector<int>> visited(n, vector<int>(3, false));
        for(int i = 0;i<redEdges.size();i++)
        {
            graph[redEdges[i][0]].push_back({redEdges[i][1], red});
        }
              
        for(int i = 0;i<blueEdges.size();i++)
        {
            graph[blueEdges[i][0]].push_back({blueEdges[i][1], blue});
        }
        
        queue<tuple<int, int,int>> q;
        q.push({0, 0, 0});
        
        vector<int> res(n, INT_MAX);
        
        while(!q.empty())
        {
            auto top = q.front();
            q.pop();
            int parent = get<0>(top);
            int step = get<1>(top);
            int color = get<2> (top);
            res[parent] = min(res[parent], step);
            if(visited[parent][color]) continue;
            visited[parent][color] = true;
            for(auto child:graph[parent])
            {
                if(color == child.second) continue;
                q.push(make_tuple(child.first, step+1, child.second));
            }
        }
        for(int i = 0;i<res.size();i++)
        {
            if(res[i]==INT_MAX) res[i] = -1;
        }
        return res;
    }
};
const RED = "red";
const BLUE = "blue";

function mapAllEdges(edges) {
    const map = new Map();
    for(let edge of edges) {
        if(!map.has(edge[0])) {
            map.set(edge[0], []);
        }
        map.get(edge[0]).push(edge[1])
    }
    return map;
}

function bfs(color, redNodeMap, blueNodeMap, result) {
    const queue = [0];
    let length = 0;
    let currentColor = color;
    while(queue.length > 0) {
        const size = queue.length;
        for(let i = 0; i < size; i++) {
            const node = queue.shift();
            if(result[node] === -1 || length < result[node] ) {
                result[node] = length;
            }
            const map = RED === currentColor ? redNodeMap : blueNodeMap;
            if(map.has(node)) {
                const edges = map.get(node);
                map.delete(node);
                queue.push(...edges)
            }
        }
        length++;
        currentColor = RED === currentColor ? BLUE : RED;
    }
    return result;
}

function shortestPath(redEdges, blueEdges, color, result) {
    const redNodeMap = mapAllEdges(redEdges);
    const blueNodeMap = mapAllEdges(blueEdges);
    bfs(color, redNodeMap, blueNodeMap, result);
}

/**
 * @param {number} n
 * @param {number[][]} redEdges
 * @param {number[][]} blueEdges
 * @return {number[]}
 */
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
    const result = new Array(n).fill(-1);
    shortestPath(redEdges, blueEdges, RED, result);
    shortestPath(redEdges, blueEdges, BLUE, result);
    return result
};
Shortest Path with Alternating Colors