1
#define red 1
2
#define blue 2
3
class Solution {
4
 public:
5
  vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges,
6
                                       vector<vector<int>> &blueEdges) {
7
    vector<vector<pair<int, int>>> graph(n);
8
    vector<vector<int>> visited(n, vector<int>(3, false));
9
    for (int i = 0; i < redEdges.size(); i++) {
10
      graph[redEdges[i][0]].push_back({redEdges[i][1], red});
11
    }
12

13
    for (int i = 0; i < blueEdges.size(); i++) {
14
      graph[blueEdges[i][0]].push_back({blueEdges[i][1], blue});
15
    }
16

17
    queue<tuple<int, int, int>> q;
18
    q.push({0, 0, 0});
19

20
    vector<int> res(n, INT_MAX);
21

22
    while (!q.empty()) {
23
      auto top = q.front();
24
      q.pop();
25
      int parent = get<0>(top);
26
      int step = get<1>(top);
27
      int color = get<2>(top);
28
      res[parent] = min(res[parent], step);
29
      if (visited[parent][color]) continue;
30
      visited[parent][color] = true;
31
      for (auto child : graph[parent]) {
32
        if (color == child.second) continue;
33
        q.push(make_tuple(child.first, step + 1, child.second));
34
      }
35
    }
36
    for (int i = 0; i < res.size(); i++) {
37
      if (res[i] == INT_MAX) res[i] = -1;
38
    }
39
    return res;
40
  }
41
};