1
class Solution {
2
  // g1-> graph with red edges
3
  // g2-> graph with blue edges
4
  List<Integer> g1[], g2[];
5
  int[] dist1, dist2, ans;
6
  int MX = (int) 2e9;
7

8
  public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
9
    dist1 = new int[n];
10
    dist2 = new int[n];
11
    g1 = new ArrayList[n];
12
    g2 = new ArrayList[n];
13
    ans = new int[n];
14
    for (int i = 0; i < n; i++) {
15
      g1[i] = new ArrayList<>();
16
      g2[i] = new ArrayList<>();
17
      dist1[i] = MX;
18
      dist2[i] = MX;
19
      ans[i] = MX;
20
    }
21
    for (int i = 0; i < redEdges.length; i++) {
22
      int u = redEdges[i][0];
23
      int v = redEdges[i][1];
24
      g1[u].add(v);
25
    }
26
    for (int i = 0; i < blueEdges.length; i++) {
27
      int u = blueEdges[i][0];
28
      int v = blueEdges[i][1];
29
      g2[u].add(v);
30
    }
31
    dist1[0] = 0;
32
    dist2[0] = 0;
33
    dfs(0, true);
34
    dfs(0, false);
35
    for (int i = 0; i < n; i++) {
36
      ans[i] = Math.min(dist1[i], dist2[i]);
37
      if (ans[i] == MX) ans[i] = -1;
38
    }
39
    return ans;
40
  }
41

42
  public void dfs(int u, boolean flag) {
43
    if (flag) {
44
      for (int v : g1[u]) {
45
        if (dist1[v] > dist2[u] + 1) {
46
          dist1[v] = dist2[u] + 1;
47
          dfs(v, !flag);
48
        }
49
      }
50
    } else {
51
      for (int v : g2[u]) {
52
        if (dist2[v] > dist1[u] + 1) {
53
          dist2[v] = dist1[u] + 1;
54
          dfs(v, !flag);
55
        }
56
      }
57
    }
58
  }
59
}