> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/shortest-path-with-alternating-colors.md).

# Shortest Path with Alternating Colors

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`

```java
class Solution {
    static class Pair {
        int val, color;

        Pair(int val, int color) {
            this.val = val;
            this.color = color;
        }
    }

    // there could be self-edges or parallel edges.
    public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
        List<Pair>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        // 0-> red, 1-> blue
        for (int[] edge : red_edges)
            graph[edge[0]].add(new Pair(edge[1], 0));
        for (int[] edge : blue_edges)
            graph[edge[0]].add(new Pair(edge[1], 1));

        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // BFS
        boolean visited[][] = new boolean[n][2];
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0, -1));
        // package ->(node, color from which we reach this node)
        int counter = 0;
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                Pair node = q.poll();
                int color = node.color;
                int val = node.val;
                if (color != -1 && visited[val][color])
                    continue;
                if (color == -1) {
                    visited[val][0] = true;
                    visited[val][1] = true;
                } else
                    visited[val][color] = true;
                ans[val] = Math.min(ans[val] == -1 ? Integer.MAX_VALUE : ans[val], counter);
                for (Pair adj : graph[val])
                    if (color == -1 || adj.color != node.color)
                        q.add(adj);
            }
            counter++;
        }
        return ans;
    }
}
```