Consider a directed graph, with nodes labelled 0, 1, ..., n-1.  In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.
Each [i, j] in red_edges denotes a red directed edge from node i to node j.  Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.
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 doesn't exist).
 
Example 1:
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]
Example 2:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]
Example 3:
Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]
Example 4:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]
Example 5:
Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

 
Constraints:

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

Difficulty: interview

Starter code:

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        

Solutions:
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        
        G = [[[], []] for i in range(n)]
        for i, j in red_edges: G[i][0].append(j)
        for i, j in blue_edges: G[i][1].append(j)
        res = [[0, 0]] + [[n * 2, n * 2] for i in range(n - 1)]
        bfs = [[0, 0], [0, 1]]
        for i, c in bfs:
            # print(i, c)
            for j in G[i][c]:
                if res[j][c] == n * 2:
                    res[j][c] = res[i][1 - c] + 1
                    bfs.append([j, 1 - c])
            # print(bfs)
        return [x if x < n * 2 else -1 for x in map(min, res)]

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # adjacent graph, branching for red/blue
        # 0 for red, 1 for blue
        G = [ [[], []] for i in range(n)]  
        for i, j in red_edges: G[i][0].append(j)
        for i, j in blue_edges: G[i][1].append(j)
        # Init res, we maintain both path-length for red & blue.
        res = [[0,0]] + [[2*n, 2*n] for i in range(n-1)] 
        # bfs : [[node, red], [node, blue]]
        bfs = [[0, 0], [0, 1]]  
        # actual BFS
        while len(bfs) > 0:
            node, color = bfs.pop(0)
            for j in G[node][color]:
                if res[j][color] == 2 * n:
                    res[j][color] = res[node][1 - color] + 1
                    bfs.append([j, 1 - color])
        
        # Select the smaller length and put in result
        return [x if x != n * 2 else -1 for x in map(min, res)]


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        edgeList = {i:[] for i in range(n)}
        
        for u, v in red_edges:
            edgeList[u].append([v, \"red\"])
        
        for u, v in blue_edges:
            edgeList[u].append([v, \"blue\"])
        
        visited = set()
        
        queue = [[0, 0, \"\"]]
        ans = [float('inf')]*n
        ans[0] = 0
        
        while queue:
            node, node_cost, prev_color = queue.pop(0)
            for dest, color in edgeList[node]:
                
                if (prev_color == \"\" or color != prev_color) and (dest, color) not in visited:
                    visited.add((dest, color))
                    queue.append([dest, node_cost+1, color])
                    ans[dest] = min(ans[dest], node_cost+1)
            
        for i in range(len(ans)):
            if ans[i] == float('inf'):
                ans[i] = -1
        return ans
            
            

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        queue = [(0, True, 0), (0, False, 0)]
        result = [-1]*n
        result[0] = 0
        visited = set()
        
        while queue:
            node, red, dist = queue.pop(0)
            if (node, red) in visited:
                continue
            visited.add((node, red))
            if red:
                for edge in blue_edges:
                    if edge[0] == node:
                        if result[edge[1]] == -1:
                            result[edge[1]] = dist + 1
                        queue.append((edge[1], False, dist+1))
            
            else:
                for edge in red_edges:
                    if edge[0] == node:
                        if result[edge[1]] == -1:
                            result[edge[1]] = dist + 1
                        queue.append((edge[1], True, dist+1))
        
        return result

import queue
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        red = self.create_adj(red_edges, n)
        blue = self.create_adj(blue_edges, n)
        
        dist_array = [-1 for _ in range(n)]
        dist_array[0] = 0
        
        q = queue.Queue()
        
        self.bfs(red, blue, \"blue\", dist_array)
        self.bfs(red, blue, \"red\", dist_array)
        
        return dist_array
        
    def bfs(self, red, blue, color, A):
        
        visited_red = set()
        visited_blue = set()
        
        q = queue.Queue()
        
        if color == \"blue\":
            visited_blue.add(0)
        else:
            visited_red.add(0)
        q.put((0,0, color))
        
        while(q.qsize() != 0):
            cur = q.get()
            cur_node = cur[0]
            cur_len = cur[1]
            cur_color = cur[2]
            
            if cur_color == \"red\":
                for node in red[cur_node]:
                    if node not in visited_red:
                        visited_red.add(node)
                        q.put((node, cur_len + 1, \"blue\"))
                        if A[node] >= 0:
                            A[node] = min(A[node], cur_len + 1)
                        else:
                            A[node] = cur_len + 1
                cur_color = \"blue\"
            else:
                for node in blue[cur_node]:
                    if node not in visited_blue:
                        visited_blue.add(node)
                        q.put((node, cur_len + 1, \"red\"))
                        if A[node] >= 0:
                            A[node] = min(A[node], cur_len + 1)
                        else:
                            A[node] = cur_len + 1
                cur_color = \"red\"
                
                
    def create_adj(self, nodes, n):
        adj = [[] for node in range(n)]
        for i in range(len(nodes)):
            adj[nodes[i][0]].append(nodes[i][1])
        return adj

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        
        self.RED = 1
        self.BLUE = -1
        self.result = [float(\"inf\")] * n
        self.result[0] = 0
        self.n = n
        self.dp = [[None] * n for _ in range(n)]
        self.visited = set()
        
        for e in red_edges:
            if self.dp[e[0]][e[1]] == None:
                self.dp[e[0]][e[1]] = list()
            self.dp[e[0]][e[1]].append(self.RED)
            
        for e in blue_edges:
            if self.dp[e[0]][e[1]] == None:
                self.dp[e[0]][e[1]] = list()
            self.dp[e[0]][e[1]].append(self.BLUE)
        
        
        q = [[0, -1], [0, 1]]
        num = 0
        
        while(len(q)):
            size = len(q)
            num += 1
            
            for _ in range(size):
                cur = q.pop(0)
                node = cur[0]
                op_c = cur[1]
                
                for i in range(1, n):
                    if self.dp[node][i] != None and op_c in self.dp[node][i]:
                        if (str(i) + str(op_c)) not in self.visited:
                            self.visited.add(str(i) + str(op_c))
                            self.result[i] = min(self.result[i], num)
                            q.append([i, op_c * -1])
                
        return [x if x != float(\"inf\") else -1 for x in self.result]
                
        
    def prettyPrint(self, dp):
        for row in dp:
            print(row)
            
            

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # 4:43 10/2/20
        out_ds = defaultdict(list)
        for i, j in red_edges:
            out_ds[i] += [('r', j)]
        for i, j in blue_edges:
            out_ds[i] += [('b', j)]
        
        # intialize queue, result list and visited list
        q = deque([(None, 0, 0)])
        res = [-1] * n
        visited = []
        while q:
            qq = deque([])
            
            # visit all nodes in q
            for last_color, e, dist in q:
                visited += [(last_color, e)]
                
                # specify the distance if hasn't been specified
                if res[e] == -1:
                    res[e] = dist
                
                # traverse all child nodes
                for color, child in out_ds[e]:
                    
                    # skip visited edges and edges with the same color as last edge
                    if color == last_color or (color, child) in visited:
                        continue
                    
                    # add child nodes to a new queue
                    qq += [(color, child, dist + 1)]
            q = qq
            
        return res
        


class Solution:
    
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        shortest = [-1] * n
        shortest[0] = 0
        
        self.BFS(shortest, red_edges, blue_edges, True)
        self.BFS(shortest, red_edges, blue_edges, False)
        
        return shortest
        
        
    def BFS(self, shortest, red_edges, blue_edges, red):
        path_len = 1
        seen_r = {0}
        seen_b = {0}
        current = [0]
        while current:
            if red:
                edges = red_edges
                seen = seen_r
                red = False
            else:
                edges = blue_edges
                seen = seen_b
                red = True
            
            new_layer = []
            for node in current:
                for edge in edges:
                    if edge[0] == node:
                        if edge[1] not in seen:
                            new_node = edge[1]
                    
                            seen.add(new_node)
                            new_layer.append(new_node)
                            if shortest[new_node] == -1:
                                shortest[new_node] = path_len
                            else:
                                shortest[new_node] = min(shortest[new_node], path_len)
                    
                            
            current = new_layer
            path_len += 1


        


import numpy as np
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # construct the graph, 1 means red edge, 2 means blue edge
        graph = collections.defaultdict(set)
        for src, des in red_edges:
            graph[src].add((des, 1))
        
        for src, des in blue_edges:
            graph[src].add((des, 2))
        seen = set()
        
        res = [-1] * n
        
        # initiate the q for bfs with node (cur Node, distanceTo0, from which color) 
        q = [(0, 0, 1), (0, 0, 2)]
        
        while q:
            nextq = []
            for cur, dist, color in q:
                # shortest distance we get so far 
                if res[cur] == -1:
                    res[cur] = dist
                for neighbor, nextColor in graph[cur]:
                    # visit the node with a different color and record the edges we have visited so far
                    if nextColor != color and (cur, neighbor, nextColor) not in seen:
                        nextq.append((neighbor, dist + 1, nextColor))
                        seen.add((cur, neighbor, nextColor))
            q = nextq
        
        return res


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        radj = [set() for i in range(n)]
        badj = [set() for i in range(n)]
        
        for x,y in red_edges :
            radj[x].add(y)
        for x,y in blue_edges :
            badj[x].add(y)
            
        def bfs(target) :
            rv = set()
            bv = set()
            from collections import deque
            que = deque([(0,-1, 0)])
            while len(que) > 0 :
                n, c, r = que.popleft()
                if c == -1 :
                    if target in radj[n] or target in badj[n] :
                        return r+1
                    for i in radj[n]:
                        que.append((i,0,r+1))
                        rv.add(i)
                    for i in badj[n]:
                        que.append((i,1,r+1))
                        bv.add(i)
                if c == 0 :
                    if target in badj[n] :
                        return r+1
                    for i in badj[n] :
                        if i not in bv :
                            bv.add(i)
                            que.append((i,1,r+1))
                if c == 1 :
                    if target in radj[n] :
                        return r+1
                    for i in radj[n] :
                        if i not in rv :
                            rv.add(i)
                            que.append((i,0,r+1))
            return -1
        res = [0]*n
        for x in range(1,n) :
            res[x] = bfs(x)
        return res


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        red = collections.defaultdict(lambda:set())
        for a,b in red_edges:
            red[a].add(b)
            
        blue = collections.defaultdict(lambda:set())
        for a,b in blue_edges:
            blue[a].add(b)
        
        # perform BFS
        seen = set()
        res = [float('inf') for _ in range(n)]
        lvl = 0
        q = collections.deque([[0,0],[0,1]]) # [node, color], 0 for red, 1 for blue
        while q:
            for _ in range(len(q)):
                n, c = q.popleft()
                seen.add((n,c))
                res[n] = min(lvl, res[n])
                if c:
                    for ch in red[n]:
                        if (ch,0) not in seen:
                            q.append([ch,0])
                else:
                    for ch in blue[n]:
                        if (ch,1) not in seen:
                            q.append([ch,1])
            lvl += 1
        
        # change all inf to -1
        for i,n in enumerate(res):
            if n == float('inf'):
                res[i] = -1
                
        return res

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # adjacent graph, branching for red/blue
        # 0 for red, 1 for blue
        G = [ [[], []] for i in range(n)]  
        for i, j in red_edges: G[i][0].append(j)
        for i, j in blue_edges: G[i][1].append(j)
        # Init res, we maintain both path-length for red & blue.
        res = [[0,0]] + [[2*n, 2*n] for i in range(n-1)] 
        # bfs : [[node, red], [node, blue]]
        bfs = [[0, 0], [0, 1]]  
        # actual BFS
        while len(bfs) > 0:
            node, color = bfs.pop(0)
            for j in G[node][color]:
                if res[j][color] == 2 * n:
                    res[j][color] = res[node][1 - color] + 1
                    bfs.append([j, 1 - color])
        
        result = []
        for length in res:
            smaller = min(length)
            if smaller < 2 * n:
                result.append(smaller)
            else:
                result.append(-1)
        
        return result


from collections import defaultdict, deque
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # we can create a directed graph with 1 as red and 0 as blue
        graph = defaultdict(list)
        for to, frm in red_edges:
            graph[to] += [[frm,1]]
        for to, frm in blue_edges:
            graph[to] += [[frm,0]]
        
        # bfs to find shortest path to each node
        paths = [-1]*n
        visited = set()
        queue = deque()
        queue.append((0, None, 0))
        
        while queue:
            curr, color, path = queue.popleft()
            if paths[curr] == -1:
                paths[curr] = path
            
            for v, c in graph[curr]:
                # if we havent visited a specific weighted edge and color is alternating allow it
                if (v, c) not in visited and (color==None or c != color):
                    queue.append((v, c, path+1))
                    visited.add((v, c))
        return paths


class Solution:
    
    def bfsHelper(self, adj_matrix, n):
        res=[1e10 for i in range(n)]
        queue=[]
        queue.append([0,0,0]) # append [node,color traversed last,dist from 0]
        visited=set() #each elem is (node, last traversed color)
        visited.add((0,0))
        while queue:
            curr,color,dist=queue.pop(0)
            res[curr]=min(res[curr], dist)
            
            for neighbor in range(n):
                edge=adj_matrix[curr][neighbor]
                if edge==0: #if there is no edge 
                    continue
                if color==0:#if we did not traverse to this node, can use any color
                    if edge in [1,2]:
                        if (neighbor,edge) not in visited:
                            visited.add((neighbor,edge))
                            queue.append([neighbor, edge, dist+1])
                    if edge==3:
                        if (neighbor,1) not in visited and color!=1:
                            visited.add((neighbor, 1))
                            queue.append([neighbor,1,dist+1])
                        if (neighbor,2) not in visited and color!=2:
                            visited.add((neighbor, 2))
                            queue.append([neighbor,2,dist+1])
                elif color in [1,2]:                       
                    if edge in [1,2]:
                        if (color != edge):
                            if (neighbor,edge) not in visited:
                                visited.add((neighbor, edge))
                                queue.append([neighbor,edge,dist+1])
                    if edge==3: #curr has red and blue edges
                        if (neighbor,1) not in visited and color!=1:
                            visited.add((neighbor, 1))
                            queue.append([neighbor,1,dist+1])
                        if (neighbor,2) not in visited and color!=2:
                            visited.add((neighbor, 2))
                            queue.append([neighbor,2,dist+1])
                            
                            
        for i in range(len(res)):
            if res[i]==1e10:
                res[i]=-1
            
        return res
                
                    
                     
    def shortestAlternatingPaths(self, n, red_edges, blue_edges):
        # 0, no edge
        # 1, red edge
        # 2, blue edge
        # 3, both edges
        adj_matrix=[[0 for i in range(n)] for j in range(n)]
        for x,y in red_edges:
            adj_matrix[x][y]+=1
        for x,y in blue_edges:
            adj_matrix[x][y]+=2
 
        return self.bfsHelper(adj_matrix, n)


from collections import defaultdict
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        red = defaultdict(list)
        blue = defaultdict(list)
        for x,y in red_edges:
            red[x].append(y)
        for x,y in blue_edges:
            blue[x].append(y)
        ans = []
        for i in range(n):
            #blue
            visited = set()
            queue = [(0,0, 0), (1,0,0)]
            level = -1
            visited.add((0,0))
            visited.add((1,0))
            while(queue):
                color, node, lvl = queue.pop(0)
                if(node == i):
                    level = lvl
                    break
                #previous is blue
                if(color == 0):
                    for neigh in red[node]:
                        if((1,neigh) not in visited):
                            queue.append((1,neigh, lvl+1))
                            visited.add((1,neigh))
                #previous is red
                elif(color == 1):
                    for neigh in blue[node]:
                        if((0,neigh) not in visited):
                            queue.append((0, neigh, lvl+1))
                            visited.add((0,neigh))
            if(level == -1):
                ans.append(-1)
            else:
                ans.append(level)
            '''             
            visited = set()
            queue = [(1,0, 0)]
            red_level = -1
            while(queue):
                color, node, lvl = queue.pop(0)
                if(node == i):
                    red_level = lvl
                    break
                #previous is blue
                if(color == 0):
                    for neigh in red[node]:
                        if((1,node,neigh) not in visited):
                            queue.append((1,neigh, lvl+1))
                            visited.add((1,node,neigh))
                #previous is red
                elif(color == 1):
                    for neigh in blue[node]:
                        if((0,node,neigh) not in visited):
                            queue.append((0, neigh, lvl+1))
                            visited.add((0,node,neigh))
            if(red_level == -1 and blue_level == -1):
                ans.append(-1)
            elif(red_level != -1 and blue_level == -1):
                ans.append(red_level)
            elif(red_level == -1 and blue_level != -1):
                ans.append(blue_level)
            else:
                ans.append(min(red_level,blue_level))'''
            
        return ans


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        g = [defaultdict(list), defaultdict(list)]
        for i, edges in enumerate([red_edges, blue_edges]):
            for u, v in edges:
                g[i][u].append(v)
        dist = [[0] + [float('inf')] * (n-1) for _ in range(2)]
        for i in range(2):
            q = deque([(0, 0, i)])
            while q:
                d, u, color = q.popleft()
                if d > dist[color][u]:
                    continue
                dist[color][u] = d
                d += 1
                color ^= 1
                for v in g[color][u]:
                    if dist[color][v] > d:
                        q.append([d, v, color])
        return [x if (x := min(a, b)) != float('inf') else -1  for a, b in zip(*dist)]

from collections import defaultdict
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        red = defaultdict(list)
        blue = defaultdict(list)
        for x,y in red_edges:
            red[x].append(y)
        for x,y in blue_edges:
            blue[x].append(y)
        ans = []
        for i in range(n):
            #blue
            visited = set()
            queue = [(0,0, 0), (1,0,0)]
            level = -1
            visited.add((0,0))
            visited.add((1,0))
            while(queue):
                color, node, lvl = queue.pop(0)
                if(node == i):
                    level = lvl
                    break
                #previous is blue
                if(color == 0):
                    for neigh in red[node]:
                        if((1,neigh) not in visited):
                            queue.append((1,neigh, lvl+1))
                            visited.add((1,neigh))
                #previous is red
                elif(color == 1):
                    for neigh in blue[node]:
                        if((0,neigh) not in visited):
                            queue.append((0, neigh, lvl+1))
                            visited.add((0,neigh))
            if(level == -1):
                ans.append(-1)
            else:
                ans.append(level)
            
        return ans


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        self.red = {}
        self.blue = {}
        for u,v in red_edges:
            if u not in self.red:
                self.red[u]=[]
            self.red[u].append(v)
            
        for u,v in blue_edges:
            if u not in self.blue:
                self.blue[u]=[]
            self.blue[u].append(v)
        
        
        def visit(i):
            if i == 0:
                return 0
            color = [self.red,self.blue]
            q = [(0,0),(0,1)]
            n=0
            visited = {}
            while len(q)>0:
                n+=1
                nxt = []
                for u,c in q: visited[(u,c)] = True
                while len(q)>0:
                    u,c = q.pop()
                    if c == 0:
                        if u in color[1]:
                            for v in color[1][u]:
                                if (v,1) not in visited:
                                    if v == i:
                                        return n
                                    else:
                                        nxt.append((v,1))
                    if c == 1:
                        if u in color[0]:
                            for v in color[0][u]:
                                if (v,0) not in visited:
                                    if v == i:
                                        return n
                                    else:
                                        nxt.append((v,0))
                q = nxt
            
            return -1
                    
                    
        result = []           
        for i in range(n):
            d = visit(i)
            result.append(d)
        return result

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        #    red -> True
        hRed = defaultdict(list)
        for edge in red_edges:
            hRed[edge[0]].append(edge[1])
        hBlue = defaultdict(list)
        for edge in blue_edges:
            hBlue[edge[0]].append(edge[1])
        def helper(n, curr, visited):
            dist = 0 
            small = float('inf')
            if curr:
                arr = deque(hRed[0])
            else:
                arr = deque(hBlue[0])
            while arr:
                size = len(arr)
                for j in range(size):
                    node = arr.popleft()
                    if (node, not curr) not in visited:
                        visited.add((node, not curr))
                        if node == i:
                            small, arr = dist + 1, []
                            break
                        if curr:
                            if node in hBlue:
                                arr += hBlue[node]
                        else:
                            if node in hRed:
                                arr += hRed[node]
                dist += 1
                curr = not curr
            return small
        res = [0]
        for i in range(1, n):
            small = helper(i, True, {(0, True)})
            small = min(small, helper(i, False, {(0, False)}))
            if small == float('inf'):
                res.append(-1)
            else:
                res.append(small)
        return res

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # adjacent graph, branching for red/blue
        # 0 for red, 1 for blue
        G = [ [[], []] for i in range(n)]  
        for i, j in red_edges: G[i][0].append(j)
        for i, j in blue_edges: G[i][1].append(j)
        # Init res, we maintain both path-length for red & blue.
        res = [[0,0]] + [[2*n, 2*n] for i in range(n-1)] 
        # bfs : [[node, red], [node, blue]]
        bfs = [[0, 0], [0, 1]]  
        # actual BFS
        while len(bfs) > 0:
            node, color = bfs.pop(0)
            for j in G[node][color]:
                if res[j][color] == 2 * n:
                    res[j][color] = res[node][1 - color] + 1
                    bfs.append([j, 1 - color])
        
        # Select the smaller length and put in result
        return [x if x < n * 2 else -1 for x in map(min, res)]


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        graph = defaultdict(set)
        
        res = [float('inf') for i in range(n)]
        
        for edge in red_edges:
            graph[edge[0]].add((edge[1],'r'))
        
        for edge in blue_edges:
            graph[edge[0]].add((edge[1],'b'))
        
        qu = [(0,0,None)]
        
        visited = set()
                
        while qu:
            node,dist,prev = qu.pop(0)
            
            res[node] = min(res[node],dist)
            
            for nbr in graph[node]:
                if prev == None or (prev != nbr[1] and (node,nbr[0],nbr[1]) not in visited):
                    qu.append((nbr[0], dist+1, nbr[1]))
                    visited.add((node,nbr[0],nbr[1]))
        
        for i in range(len(res)):
            if res[i] == float('inf'):
                res[i] = -1
                
        return res
        
        


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        graph_red = defaultdict(list)
        graph_blue = defaultdict(list)
        
        for a, b in red_edges:
            graph_red[a].append(b)
        
        for a, b in blue_edges:
            graph_blue[a].append(b)
            
        def bfs(target):
            BLUE = 1
            RED = 2
            seen = set()
            queue = deque([(0, 0, BLUE), (0,0,RED)])
            
            while queue:
                node, steps, color = queue.popleft()
                
                if node == target:
                    return steps
                
                if color == RED:
                    for next_node in graph_blue[node]:
                        if (next_node, BLUE) not in seen:
                            seen.add((next_node, BLUE))
                            queue.append((next_node, steps + 1, BLUE))
                else:
                    for next_node in graph_red[node]:
                        if (next_node, RED) not in seen:
                            seen.add((next_node, RED))
                            queue.append((next_node, steps + 1, RED))
            
            return -1
                            
            
        res = []
        
        for i in range(n):
            res.append(bfs(i))
        
        return res

class Solution:
    def shortestAlternatingPaths(
        self, 
        n: int, 
        red_edges: List[List[int]], 
        blue_edges: List[List[int]],
    ) -> List[int]:
        red_adj = [[] for i in range(n)]
        blue_adj = [[] for i in range(n)]
        for edge in red_edges:
            red_adj[edge[0]].append(edge[1])
        for edge in blue_edges:
            blue_adj[edge[0]].append(edge[1])
        result = []
        for i in range(n):
            start_red = self.shortestPath(red_adj, blue_adj, True, i)
            start_blue = self.shortestPath(red_adj, blue_adj, False, i)
            if start_red == -1:
                result.append(start_blue)
            elif start_blue == -1:
                result.append(start_red)
            elif start_red < start_blue:
                result.append(start_red)
            else:
                result.append(start_blue)
        return result
        
    def shortestPath(
        self,
        red_adj: List[List[int]], 
        blue_adj: List[List[int]],
        startRed: bool,
        X: int,
    ) -> int:
        red_visited = set()
        blue_visited = set()
        bfs = [(0, startRed, 0)]
        while len(bfs) > 0:
            node, is_red, depth = bfs.pop(0)
            if node == X:
                return depth
            if is_red and node in red_visited:
                continue
            elif not is_red and node in blue_visited:
                continue
            if is_red:
                red_visited.add(node)
                for n in blue_adj[node]:
                    if n not in blue_visited:
                        bfs.append((n, False, depth + 1))
            else:
                blue_visited.add(node)
                for n in red_adj[node]:
                    if n not in red_visited:
                        bfs.append((n, True, depth + 1))
        return -1

class Solution:
    def shortestAlternatingPaths(self, n: int,
                                 red_edges: List[List[int]],
                                 blue_edges: List[List[int]]) -> List[int]:
        g = {}
        for s,e in red_edges:
            if s not in g:
                g[s] = []
            g[s].append((e, 'r'))
        for s,e in blue_edges:
            if s not in g:
                g[s] = []
            g[s].append((e, 'b'))
        return [find_path_length(g, 0, i) for i in range(0, n)]
    
def find_path_length(g, s, e):
    to_visit = [(s, 0, 'r'), (s, 0, 'b')]
    visited = set()
    while to_visit:
        x, i, c = to_visit.pop(0)
        if (x,c) in visited:
            continue
        visited.add((x,c))
        if x == e:
            return i
        if x not in g:
            continue
        for s1, c1 in g[x]:
            if c != c1:
                to_visit.append((s1, i+1, c1))
    return -1


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        G = [[] for _ in range(n)]
        for x,y in red_edges: G[x].append((y,1))
        for x,y in blue_edges: G[x].append((y,-1))
        def bfs(target):
            if target==0: return 0
            q = deque([(y,color) for y,color in G[0]])
            level = 1
            visited = set()
            while q:
                l = len(q)
                for _ in range(l):
                    curr,color = q.popleft()
                    visited.add((curr,color))
                    if curr == target: return level
                    for y,z in G[curr]:
                        if z!=color and (y,z) not in visited: q.append((y,z))
                level+=1
            return -1
        return [bfs(i) for i in range(0,n)]

from collections import deque
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        edges = [{}, {}]
        for i, allEdges in enumerate([red_edges, blue_edges]):
            for edge in allEdges:
                src, tar = edge[0], edge[1]
                edges[i].setdefault(src, []).append(tar)
        def shortedAlterPath(source, target, colour): # dfs
            queue = deque([source])
            visited = {(colour, source)}
            count = 0
            while queue:
                for _ in range(len(queue)):
                    node = queue.popleft()
                    if node == target: return count
                    for nextNode in edges[colour].get(node, []):
                        if (1 - colour, nextNode) in visited: continue
                        visited.add((1 - colour, nextNode))
                        queue.append(nextNode)
                colour = 1 - colour
                count += 1
            return float('inf')
        res = [0] * n
        for dst in range(1, n):
            distance = min(
                shortedAlterPath(0, dst, 0),
                shortedAlterPath(0, dst, 1)
            )
            if distance == float('inf'): res[dst] = -1
            else: res[dst] = distance
        return res


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        G = [[] for _ in range(n)]
        for x,y in red_edges: G[x].append((y,1))
        for x,y in blue_edges: G[x].append((y,-1))
        def bfs(target):
            if target==0: return 0
            q = deque([(y,color,1) for y,color in G[0]])
            visited = set()
            while q:
                l = len(q)
                curr,color,level = q.popleft()
                visited.add((curr,color))
                if curr == target: return level
                for y,z in G[curr]:
                    if z!=color and (y,z) not in visited: q.append((y,z,level+1))
            return -1
        return [bfs(i) for i in range(0,n)]

class Solution:
    # TLE
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        '''
        O(N^3)
        
        Variation of Floyd.
        
        DP.
        
        dp[k, i, j, c1, c2]:
        shortest path between i and j, 
        with first edge being c1 and last edge being color c2, 
        using first k nodes as intermediary.
        
        Transition: 
        - for each k, try if it it is an improvement for (i, j, c1, c2)
        - 1) 
          - dp[k - 1, i, k, c1, 0] + dp[k - 1, k, j, 1, c2] -- use k to improve
          - dp[k - 1, i, k, c1, 1] + dp[k - 1, k, j, 0, c2] -- use k to improve
        - 2) dp[k - 1, i, j, c1, c2] -- do not use k (but used up to k-1) 
        
        Since k is executed in increasing order, we can remove this dimension by rollling array.
        
        Use dict(<i, j, c1, c2>) to store the state.
        
        '''
        
        MAX = float('inf')
        
        state = {}
        for i in range(n):
            for j in range(n):
                for c1 in range(2):
                    for c2 in range(2):
                        state[(i, j, c1, c2)] = MAX
        
        for u, v in red_edges:
            state[(u, v, 0, 0)] = 1
            # state[(v, u, 0, 0)] = 1
        for u, v in blue_edges:
            state[(u, v, 1, 1)] = 1
            # state[(v, u, 1, 1)] = 1
                        
        def relax(k):
            for i in range(n):
                for j in range(n):
                    for c1 in range(2):
                        for c2 in range(2):
                            state[(i, j, c1, c2)]  = min(
                                state[(i, j, c1, c2)],
                                state[(i, k, c1, 0)] + state[(k, j, 1, c2)],
                                state[(i, k, c1, 1)] + state[(k, j, 0, c2)]
                            )

        for k in range(0, n):
            # if k == 5:
            #     print(state[(5, 5, 0, 0)])
            #     print(state[(5, 5, 1, 1)])
            #     print(state[(0, 5, 1, 0)])
            #     print(state[(0, 5, 1, 1)])
            #     print(state[(5, 2, 0, 0)])
            #     print(state[(5, 2, 1, 0)])
            relax(k)
          
        # print('end', state[(5, 2, 1, 0)])
        
        for k in range(0, n):
            relax(k)
            
        # print('end', state[(5, 2, 1, 0)])

        ans = [0]
        for i in range(1, n):
            t = min(state[(0, i, c1, c2)] for c1 in range(2) for c2 in range(2))
            if t == MAX:
                t = -1
            ans.append(t)
            
        return ans

            

'''
3
[[0,1],[1,2]]
[]
3
[[0,1]]
[[2,1]]
3
[[1,0]]
[[2,1]]
3
[[0,1]]
[[1,2]]
3
[[0,1],[0,2]]
[[1,0]]
5
[[0,1],[1,2],[0,3],[4,2]]
[[3,4]]
6
[[4,1],[3,5],[5,2],[1,4],[4,2],[0,0],[2,0],[1,1]]
[[5,5],[5,0],[4,4],[0,3],[1,0]]
100
[[42,98],[85,41],[71,93],[2,38],[51,81],[0,17],[62,95],[76,15],[96,12],[98,38],[22,22],[26,65],[32,81],[23,33],[95,3],[18,8],[14,49],[60,23],[47,18],[38,82],[22,53],[6,79],[54,81],[37,44],[20,75],[22,33],[70,20],[94,24],[75,44],[19,78],[17,58],[11,47],[18,30],[17,65],[43,1],[18,5],[0,68],[82,75],[66,12],[41,67],[41,86],[37,48],[86,89],[41,1],[28,68],[19,47],[97,60],[59,3],[0,19],[77,91],[77,34]]
[[61,11],[34,19],[18,61],[45,60],[80,28],[33,6],[51,45],[54,56],[42,12],[8,4],[74,64],[57,66],[98,25],[40,84],[2,34],[80,41],[35,47],[5,19],[87,32],[6,3],[64,94],[60,67],[75,95],[72,6],[89,0],[44,63],[27,62],[56,54],[26,9],[46,66],[79,40],[83,14],[44,73],[93,77],[14,48],[65,20],[57,30],[99,46],[85,80],[25,24],[99,4],[6,45],[25,51],[47,44]]
'''    
        

class Solution:
    #AC
    # Runtime: 144 ms, faster than 22.01% of Python3 online submissions for Shortest Path with Alternating Colors.
    # Memory Usage: 14.2 MB, less than 10.36% of Python3 online submissions for Shortest Path with Alternating Colors.
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        '''
        modified SPFA (Dijkstra)
        
        PriorityQueue element: (node, end_edge_color).
        O(M log M)
        '''
        
        MAX = float('inf')
        
        from collections import defaultdict
        adj = defaultdict(set)
        for u, v in red_edges:
            adj[u].add((v, 0))
        for u, v in blue_edges:
            adj[u].add((v, 1))
            
        from queue import PriorityQueue
        pq = PriorityQueue()
        pq.put((0, 0, 0)) # distance, node, color
        pq.put((0, 0, 1))
        dist = {}
        for u in range(n):
            for c in range(2):
                dist[(u, c)] = MAX
        dist[(0, 0)] = 0
        dist[(0, 1)] = 0
        # solved = {}
        solved = set()
        while not pq.empty():
            d, u, c = pq.get()
            # solved[(u, c)] = d
            for v, cc in adj[u]:
                if cc != c:
                    if dist[(v, cc)] > d + 1:
                        dist[(v, cc)] = d + 1
                        pq.put((d + 1, v, cc))
        
        ans = []
        for u in range(n):
            t = min(dist[(u, 0)], dist[(u, 1)])
            if t == MAX:
                t = -1
            ans.append(t)
        
        return ans


    
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        '''
        Idea: We can switch edge and node.
        
        In the new graph definition:
        - node: original edges, regardless of their color
        - edge: 
            we test all pairs of original incident edges (now node) at one original node, 
            build an edge if they are of different color
        
        Run normal SP algorithm on the resulting graph.
        '''
        
        from collections import defaultdict
        ri, ro, bi, bo = defaultdict(list), defaultdict(list), defaultdict(list), defaultdict(list)
        
        nodes = set()
        for (i, (u, v)) in enumerate(red_edges):
            nodes.add(('r', i))
            ro[u].append(('r', i))
            ri[v].append(('r', i))
        for (i, (u, v)) in enumerate(blue_edges):
            nodes.add(('b', i))
            bo[u].append(('b', i))
            bi[v].append(('b', i))
        
        graph = defaultdict(set)
        for i in range(n):
            for u in ri[i]:
                for v in bo[i]:
                    graph[u].add(v)
            for u in bi[i]:
                for v in ro[i]:
                    graph[u].add(v)
        
        nodes.add('S')
        for u in ro[0]:
            graph['S'].add(u)
        for u in bo[0]:
            graph['S'].add(u)
            
        INF = float('inf')
        dist = {}
        for u in nodes:
            dist[u] = INF
        dist['S'] = 0
        
        from queue import PriorityQueue
        pq = PriorityQueue()
        pq.put((0, 'S'))
        solved = set()
        while len(solved) < len(nodes) and not pq.empty():
            d, u = pq.get()
            solved.add(u)
            for v in graph[u]:
                if dist[u] + 1 < dist[v]:
                    dist[v] = d + 1
                    pq.put((d + 1, v))
        
        ans = [0]
        for i in range(1, n):
            rd = [dist[u] for u in ri[i]]
            bd = [dist[u] for u in bi[i]]
            if len(rd + bd) == 0:
                t = -1
            else:
                t = min(rd + bd)
                if t == INF:
                    t = -1
            ans.append(t)
        
        return ans
            
        
        


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        distance = [[float('inf'), float('inf')] for _ in range(n)]
        distance[0][0] = 0 # red
        distance[0][1] = 0 # blue
        
        for _ in range(n):
            for u, v in red_edges:
                if distance[u][1] + 1 < distance[v][0]:
                    distance[v][0] = distance[u][1] + 1
            for u, v in blue_edges:
                if distance[u][0] + 1 < distance[v][1]:
                    distance[v][1] = distance[u][0] + 1
        
        min_distance = []
        for d in distance:
            min_d = min(d)
            if min_d < float('inf'):
                min_distance.append(min_d)
            else:
                min_distance.append(-1)
        return min_distance
        
'''

distance[X][0] distance upto X with last edge red
distance[X][1]                      last edge blue



'''

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        def bfs(target, color):
            q = deque([[0, 0, color]])
            seen = set()
            while q:
                cur, step, c = q.popleft()
                if cur == target:
                    return step
                if (cur, c) in seen:
                    continue
                seen.add((cur, c))
                
                for neighbor in e[cur][c]:
                    q.append([neighbor, step + 1, (c + 1) % 2])
                    
            return -1
        
        e = {i: [set(), set()] for i in range(n)}
        for i, j in red_edges:
            e[i][0].add(j)
        for i, j in blue_edges:
            e[i][1].add(j)
            
        # print(e)
        res = [0] * n
        for i in range(1, n):
            red = bfs(i, 0)
            blue = bfs(i, 1)
            if red == -1:
                res[i] = blue
            elif blue == -1:
                res[i] = red
            else:
                res[i] = min(red, blue)
            
        return res



from collections import defaultdict

class Graph:
    def __init__(self):
        self.edges = defaultdict(list)
    def add_edge(self,src,dst,color):
        self.edges[src].append((dst,color))
        

class Solution:     
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        g = Graph()
        for src,dst in red_edges:
            g.add_edge(src,dst,\"R\")
        for src,dst in blue_edges:
            g.add_edge(src,dst,\"B\")
        
        
        data = [float(inf)]*(n)
        q = deque()
        q.append((0,0,None))
        visited = set()
        while(q):
            node,dist,prevColor = q.popleft()
            visited.add((node,prevColor))
            if(dist < data[node]):
                data[node] = dist
            
            for nei,col in g.edges[node]:
                if col!=prevColor and (nei,col) not in visited:
                    q.append((nei,dist+1,col))
        
        for i,e in enumerate(data):
            if e==float('inf'):
                data[i]=-1
        
        return data
                    
            
            

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        combined = collections.defaultdict(lambda: [set(), set()])
        
        for i,j in red_edges:
            combined[i][0].add(j)
        for i,j in blue_edges:
            combined[i][1].add(j)
            
        ans = collections.defaultdict(lambda: float('inf'))
            
        # 0 = red, 1 = blue
        
        def bfs(queue):
            seen = set()
            while queue:
                size = len(queue)
                for _ in range(size):
                    cur, distance, color = queue.popleft()
                    ans[cur] = min(ans[cur], distance)
                    for nb in combined[cur][color]:
                        if (cur,nb,color) not in seen:
                            seen.add((cur,nb,color))
                            queue.append((nb, distance + 1, abs(1-color)))
        
        bfs(collections.deque([(0,0,0)]))
        bfs(collections.deque([(0,0,1)]))
        
        return [-1 if i not in ans else ans[i] for i in range(n)]
                    
                
                


import queue
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        
        red = self.create_adj(red_edges, n)
        blue = self.create_adj(blue_edges, n)
        
        dist_array = [-1 for _ in range(n)]
        dist_array[0] = 0
        q = queue.Queue()
        self.bfs(red, blue, \"blue\", dist_array)
        self.bfs(red, blue, \"red\", dist_array)
        return dist_array
        
    def bfs(self, red, blue, color, A):
        visited_red = set()
        visited_blue = set()
        q = queue.Queue()
        if color == \"blue\":
            visited_blue.add(0)
        else:
            visited_red.add(0)
        q.put((0,0, color))
        
        while(q.qsize() != 0):
            cur = q.get()
            cur_node = cur[0]
            cur_len = cur[1]
            cur_color = cur[2]
            if cur_color == \"red\":
                for node in red[cur_node]:
                    if node not in visited_red:
                        visited_red.add(node)
                        q.put((node, cur_len + 1, \"blue\"))
                        if A[node] >= 0:
                            A[node] = min(A[node], cur_len + 1)
                        else:
                            A[node] = cur_len + 1
                cur_color = \"blue\"
            else:
                for node in blue[cur_node]:
                    if node not in visited_blue:
                        visited_blue.add(node)
                        q.put((node, cur_len + 1, \"red\"))
                        if A[node] >= 0:
                            A[node] = min(A[node], cur_len + 1)
                        else:
                            A[node] = cur_len + 1
                cur_color = \"red\"
        

        
        
        
    def create_adj(self, nodes, n):
        adj = [[] for node in range(n)]
        for i in range(len(nodes)):
            adj[nodes[i][0]].append(nodes[i][1])
        
        return adj

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        result = [-1] * n
        
        
        redDict = defaultdict(list)
        
        for edge in red_edges:
            redDict[edge[0]].append(edge[1])
        
        blueDict = defaultdict(list)
        
        for edge in blue_edges:
            blueDict[edge[0]].append(edge[1])
        
        queue = deque()
        
        queue.append((0, 'blue', 0))
        queue.append((0, 'red', 0))
        # result[0] = 0
        
        while queue:
            item = queue.popleft()
            if result[item[0]] == -1 or result[item[0]] >= item[2]:
                result[item[0]] = item[2]
            if item[1] == 'blue':
                nextColor = 'red'
                nextNodes = blueDict[item[0]]
            else:
                nextColor = 'blue'
                nextNodes = redDict[item[0]]
            
            for nex in range(len(nextNodes)):
                if nextNodes[nex] != -1:
                    queue.append((nextNodes[nex], nextColor, item[2]+1))
                    nextNodes[nex] = -1
                
        return result

class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        # 4:43 10/2/20
        graph = [collections.defaultdict(set), collections.defaultdict(set)]

        for i, j in red_edges:
            graph[0][i].add(j)

        for i, j in blue_edges:
            graph[1][i].add(j)

        ans = [math.inf] * n
        
        stack = [(0, 0, 0), (1, 0, 0)]
        
        for color, node, dist in stack:
            ans[node] = min(ans[node], dist)
            neighbors = list(graph[color][node])
            for nei in neighbors:
                graph[color][node].remove(nei)
                stack.append((1-color, nei, dist+1))
        
        return [-1 if x == math.inf else x for x in ans]