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: MEDIUM
Tags: Graph algorithms

Graph traversal

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:
			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])
		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]:
		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]] + [[2 * n, 2 * n] for i in range(n - 1)]
		bfs = [[0, 0], [0, 1]]
		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])
		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]:
		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


class Solution:

	def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
		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)]
		q = deque([(None, 0, 0)])
		res = [-1] * n
		visited = []
		while q:
			qq = deque([])
			for (last_color, e, dist) in q:
				visited += [(last_color, e)]
				if res[e] == -1:
					res[e] = dist
				for (color, child) in out_ds[e]:
					if color == last_color or (color, child) in visited:
						continue
					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]:
		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
		q = [(0, 0, 1), (0, 0, 2)]
		while q:
			nextq = []
			for (cur, dist, color) in q:
				if res[cur] == -1:
					res[cur] = dist
				for (neighbor, nextColor) in graph[cur]:
					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)
		seen = set()
		res = [float('inf') for _ in range(n)]
		lvl = 0
		q = collections.deque([[0, 0], [0, 1]])
		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
		for (i, n) in enumerate(res):
			if n == float('inf'):
				res[i] = -1
		return res


from collections import defaultdict, deque

class Solution:

	def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		for (to, frm) in red_edges:
			graph[to] += [[frm, 1]]
		for (to, frm) in blue_edges:
			graph[to] += [[frm, 0]]
		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 (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 = [10000000000.0 for i in range(n)]
		queue = []
		queue.append([0, 0, 0])
		visited = set()
		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:
					continue
				if color == 0:
					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:
						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] == 10000000000.0:
				res[i] = -1
		return res

	def shortestAlternatingPaths(self, n, red_edges, blue_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):
			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
				if color == 0:
					for neigh in red[node]:
						if (1, neigh) not in visited:
							queue.append((1, neigh, lvl + 1))
							visited.add((1, neigh))
				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]:
		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)]


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]:
		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]
						elif 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]:
		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):
			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]:
		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
		for (u, v) in blue_edges:
			state[u, v, 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):
			relax(k)
		for k in range(0, n):
			relax(k)
		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

class Solution:

	def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
		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))
		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 = set()
		while not pq.empty():
			(d, u, c) = pq.get()
			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]:
		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
		distance[0][1] = 0
		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


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)
		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


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'))

		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)]


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))
		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]:
		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]