enum class Color { WHITE, RED, GREEN };

class Solution {
 public:
  bool isBipartite(vector<vector<int>>& graph) {
    vector<Color> colors(graph.size(), Color::WHITE);

    for (int i = 0; i < graph.size(); ++i) {
      // already colored, do nothing
      if (colors[i] != Color::WHITE)
        continue;
      // colors[i] == Color::WHITE
      colors[i] = Color::RED;  // always paint w/ Color::RED
      // BFS
      queue<int> q{{i}};
      while (!q.empty()) {
        const int u = q.front();
        q.pop();
        for (const int v : graph[u]) {
          if (colors[v] == colors[u])
            return false;
          if (colors[v] == Color::WHITE) {
            colors[v] = colors[u] == Color::RED ? Color::GREEN : Color::RED;
            q.push(v);
          }
        }
      }
    }

    return true;
  }
};

enum Color { WHITE, RED, GREEN }

class Solution {
  public boolean isBipartite(int[][] graph) {
    Color[] colors = new Color[graph.length];
    Arrays.fill(colors, Color.WHITE);

    for (int i = 0; i < graph.length; ++i) {
      // already colored, do nothing
      if (colors[i] != Color.WHITE)
        continue;
      // colors[i] == Color.WHITE
      colors[i] = Color.RED; // always paint w/ Color.RED
      // BFS
      Queue<Integer> q = new ArrayDeque<>(Arrays.asList(i));
      while (!q.isEmpty()) {
        for (int sz = q.size(); sz > 0; --sz) {
          final int u = q.poll();
          for (final int v : graph[u]) {
            if (colors[v] == colors[u])
              return false;
            if (colors[v] == Color.WHITE) {
              colors[v] = colors[u] == Color.RED ? Color.GREEN : Color.RED;
              q.offer(v);
            }
          }
        }
      }
    }

    return true;
  }
}

from enum import Enum


class Color(Enum):
  WHITE = 0
  RED = 1
  GREEN = 2


class Solution:
  def isBipartite(self, graph: List[List[int]]) -> bool:
    colors = [Color.WHITE] * len(graph)

    for i in range(len(graph)):
      # already colored, do nothing
      if colors[i] != Color.WHITE:
        continue
      # colors[i] == Color.WHITE
      colors[i] = Color.RED  # always paint w/ Color.RED
      # BFS
      q = deque([i])
      while q:
        u = q.popleft()
        for v in graph[u]:
          if colors[v] == colors[u]:
            return False
          if colors[v] == Color.WHITE:
            colors[v] = Color.RED if colors[u] == Color.GREEN else Color.GREEN
            q.append(v)

    return True

enum class Color { WHITE, RED, GREEN };

class Solution {
 public:
  bool isBipartite(vector<vector<int>>& graph) {
    vector<Color> colors(graph.size(), Color::WHITE);

    for (int i = 0; i < graph.size(); ++i)
      if (colors[i] == Color::WHITE &&
          !isValidColor(graph, i, colors, Color::RED))
        return false;

    return true;
  }

 private:
  bool isValidColor(const vector<vector<int>>& graph, int u,
                    vector<Color>& colors, Color color) {
    // the painted color should be same as the `color`
    if (colors[u] != Color::WHITE)
      return colors[u] == color;

    colors[u] = color;  // always paint w/ `color`

    // all children should have valid colors
    for (const int v : graph[u])
      if (!isValidColor(graph, v, colors,
                        color == Color::RED ? Color::GREEN : Color::RED))
        return false;

    return true;
  }
};

enum Color { WHITE, RED, GREEN }

class Solution {
  public boolean isBipartite(int[][] graph) {
    Color[] colors = new Color[graph.length];
    Arrays.fill(colors, Color.WHITE);

    for (int i = 0; i < graph.length; ++i)
      if (colors[i] == Color.WHITE && !isValidColor(graph, i, colors, Color.RED))
        return false;

    return true;
  }

  private boolean isValidColor(int[][] graph, int u, Color[] colors, Color color) {
    // the painted color should be same as the `color`
    if (colors[u] != Color.WHITE)
      return colors[u] == color;

    colors[u] = color; // always paint w/ `color`

    // all children should have valid colors
    for (final int v : graph[u])
      if (!isValidColor(graph, v, colors, color == Color.RED ? Color.GREEN : Color.RED))
        return false;

    return true;
  }
}

from enum import Enum


class Color(Enum):
  WHITE = 0
  RED = 1
  GREEN = 2


class Solution:
  def isBipartite(self, graph: List[List[int]]) -> bool:
    colors = [Color.WHITE] * len(graph)

    def isValidColor(u: int, color: Color) -> bool:
      # the painted color should be same as the `color`
      if colors[u] != Color.WHITE:
        return colors[u] == color

      colors[u] = color  # always paint w/ `color`

      # all children should have valid colors
      childrenColor = Color.RED if colors[u] == Color.GREEN else Color.GREEN
      return all(isValidColor(v, childrenColor) for v in graph[u])

    return all(colors[i] != Color.WHITE or isValidColor(i, Color.RED)
               for i in range(len(graph)))