def shortestAlternatingPaths(n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
# make both graph first
red, blue = defaultdict(set), defaultdict(set)
for src, snk in redEdges:
red[src].add(snk)
for src, snk in blueEdges:
blue[src].add(snk)
answer = [-1] * n
q = deque()
q.append((0, 0, -1)) # contains a pair of (node, length, color) where -1:red, 1:blue
q.append((0, 0, 1))
red_visit, blue_visit = {0}, {0}
while q:
node, length, color = q.popleft()
answer[node] = length if answer[node] < 0 else min(answer[node], length)
graph = blue if color == 1 else red
visited = blue_visit if color == 1 else red_visit
for neighbor in graph[node]:
if neighbor in visited:
continue
visited.add(neighbor)
q.append((neighbor, length + 1, -color))
return answer