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

<p>You are given two arrays <code>redEdges</code> and <code>blueEdges</code> where:</p>

<ul>
	<li><code>redEdges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is a directed red edge from node <code>a<sub>i</sub></code> to node <code>b<sub>i</sub></code> in the graph, and</li>
	<li><code>blueEdges[j] = [u<sub>j</sub>, v<sub>j</sub>]</code> indicates that there is a directed blue edge from node <code>u<sub>j</sub></code> to node <code>v<sub>j</sub></code> in the graph.</li>
</ul>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
<strong>Output:</strong> [0,1,-1]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
<strong>Output:</strong> [0,1,-1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= redEdges.length,&nbsp;blueEdges.length &lt;= 400</code></li>
	<li><code>redEdges[i].length == blueEdges[j].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub>, u<sub>j</sub>, v<sub>j</sub> &lt; n</code></li>
</ul>

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        # shortest path from node 0 to node x, such that colors alternate, or -1 if path not exist
        # edges do not have weights, directed
        answer_red = [-1] * n #distance from node 0 by alternating ages.
        answer_blue = [-1] * n 
        # Will also check visited with answer array
        
        #BFS, explore only alternating paths
        # If I visit a node -> it contains answer, don't need to recheck
        # red_list, blue_list -- nodes visited with red/blue edge previously
        # during BFS, I firslty take red, add all new_nodes to tmp_blue, then expolore blue, add to red, then blue_list = tmp_blue
        # Even if a node was visited by red, and has a distance, we still need to check blue paths that can be several steps further

        # Construct the graph
        # n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
        red_graph = defaultdict(list) # node -> list of nodes
        blue_graph = defaultdict(list)
        for a,b in redEdges:
            red_graph[a].append(b)
        for a,b in blueEdges:
            blue_graph[a].append(b)
        
        red_list = [(0,0)]
        blue_list = [(0,0)]

        while red_list or blue_list:
            tmp_blue = []
            for v1, d1 in red_list: #Previous was red # (1,1)
                if answer_red[v1] == -1:
                    answer_red[v1] = d1
                for v2 in blue_graph[v1]:
                    if answer_blue[v2] == -1: # Not visited
                        tmp_blue.append((v2, d1+1))
            tmp_red = [] 
            for v1, d1 in blue_list:
                if answer_blue[v1] == -1:
                    answer_blue[v1] = d1
                for v2 in red_graph[v1]:
                    if answer_red[v2] == -1:
                        tmp_red.append((v2,d1+1))
            red_list = tmp_red
            blue_list = tmp_blue
        answer = []
        for a,b in zip(answer_red, answer_blue):
            if a == -1 and b == -1:
                answer.append(-1)
            elif a == -1:
                answer.append(b)
            elif b == -1:
                answer.append(a)
            else:
                answer.append(min(a,b))
        return answer



16800