"""
在一个有向图中，节点分别标记为 0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色，且存在自环或平行边。

red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

 

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]
示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]
示例 3：

输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]
示例 4：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]
示例 5：

输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]
 

提示：

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
通过次数4,980提交次数13,557

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-with-alternating-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import *


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        red_g, blue_g = [[0 for _ in range(n)] for _ in range(n)], [[0 for _ in range(n)] for _ in range(n)]
        for edge in red_edges:
            red_g[edge[0]][edge[1]] = 1
        for edge in blue_edges:
            blue_g[edge[0]][edge[1]] = 1

        red_first, blue_first = [-1 for _ in range(n)], [-1 for _ in range(n)]

        q, red, cur_len = [(0, 0)], True, 0
        while len(q) > 0:
            cur_node, l = q.pop()
            if red:
                for i in range(n):
                    if red_g[cur_node][i] and red_first[i] == -1:
                        q.insert(0, (i, l + 1))
                        red_first[i] = l + 1
                red = False
            else:
                for i in range(n):
                    if blue_g[cur_node][i] and red_first[i] == -1:
                        q.insert(0, (i, l + 1))
                        red_first[i] = l + 1
                red = True

        q, blue, cur_len = [(0, 0)], True, 0
        while len(q) > 0:
            cur_node, l = q.pop()
            if blue:
                for i in range(n):
                    if blue_g[cur_node][i] and blue_first[i] == -1:
                        q.insert(0, (i, l + 1))
                        blue_first[i] = l + 1
                blue = False
            else:
                for i in range(n):
                    if red_g[cur_node][i] and blue_first[i] == -1:
                        q.insert(0, (i, l + 1))
                        blue_first[i] = l + 1
                blue = True

        rtn = [0]
        for i in range(1, n):
            cur = min(red_first[i], blue_first[i])
            if cur == -1:
                cur = max(red_first[i], blue_first[i])
            rtn.append(cur)
        return rtn


if __name__ == '__main__':
    s = Solution()
    print(s.shortestAlternatingPaths(3, [[0,1]], [[1, 2]]))
