from typing import List
from collections import deque
class Node:
  def __init__(self, val = 0):
    self.redEdges = set()
    self.blueEdges = set()
    self.val = val
class Solution:
  def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
    visitRed = [False] * n
    visitBlue = [False] * n
    nodes = [None] * n
    visited = [-1] * n
    visited[0] = 0
    for i in range(n):
      nodes[i] = Node(i)
    
    for edge in red_edges:
      nodes[edge[0]].redEdges.add(edge[1])
    for edge in blue_edges:
      nodes[edge[0]].blueEdges.add(edge[1])
      
    queue = deque()
    for n in nodes[0].redEdges:
      queue.append([n, 'Red', 1])
    for n in nodes[0].blueEdges:
      queue.append([n, 'Blue', 1])
      
    while queue:
      node, color, l = queue.popleft()
      if color == 'Red':
        if visitRed[node]:
          continue
        visitRed[node] = True
        for n in nodes[node].blueEdges:
          queue.append([n, 'Blue', l+1])
      elif color == 'Blue':
        if visitBlue[node]:
          continue
        visitBlue[node] = True
        for n in nodes[node].redEdges:
          queue.append([n, 'Red', l+1])
      if visited[node] == -1:
        visited[node] = l
          
    return visited