#include "Alice.h"

namespace {
int sample_variable = 0;
void sample_function() {}
} // namespace

std::vector<int> Alice(int N, int M, std::vector<int> U, std::vector<int> V,
                       std::vector<int> C) {
  std::vector<int> deg(N);
  for (int i = 0; i < M; ++i) {
    deg[U[i]]++;
    deg[V[i]]++;
  }
  std::vector<int> &ans = V;
  ans.resize(0);
  for (int i = 0; i < N; ++i) {
    if (deg[i] >= 8) {
      ans.push_back(C[i] >= 4);
      ans.push_back((C[i] / 2) % 2 == 0);
    }
  }
  return ans;
}

#include "Bob.h"
#include <queue>

namespace {
int sample_variable = 0;
void sample_function() {}
} // namespace

std::vector<int> Bob(int N, int M, std::vector<int> U, std::vector<int> V,
                     std::vector<int> X) {
  std::vector<std::vector<int>> adj(N);
  for (int i = 0; i < M; ++i) {
    adj[U[i]].push_back(V[i]);
    adj[V[i]].push_back(U[i]);
  }

  std::vector<int> &C = V;
  {
    std::vector<int> ind(N, -1);
    {
      int cnt = 0;
      for (int i = 0; i < N; ++i) {
        if ((int)adj[i].size() >= 8) {
          ind[i] = cnt;
          cnt++;
          adj[i].clear();
        }
      }
    }
    std::vector<std::vector<int>> bp(N);
    // for (int i = 0; i < N; ++i) {
    //   if (ind[i] == -1)
    //     continue;
    //   for (int j : adj[i]) {
    //     if (ind[j] == -1)
    //       continue;
    //     if (X[2 * ind[i]] != X[2 * ind[j]] ||
    //         X[2 * ind[i] + 1] != X[2 * ind[j] + 1]) {
    //       continue;
    //     }
    //     bp[i].push_back(j);
    //   }
    // }
    for (int i = 0; i < M; ++i) {
      if (ind[U[i]] == -1 || ind[V[i]] == -1)
        continue;
      if (X[2 * ind[U[i]]] != X[2 * ind[V[i]]])
        continue;
      if (X[2 * ind[U[i]] + 1] != X[2 * ind[V[i]]] + 1)
        continue;
      bp[U[i]].push_back(V[i]);
      bp[V[i]].push_back(U[i]);
    }

    U.clear();
    V.clear();
    std::vector<bool> vis(N);
    C.assign(N, -1);
    std::vector<int> &q = U;
    q.clear();
    q.reserve(N);
    int ii = 0;
    for (int s = 0; s < N; ++s) {
      if (ind[s] != -1 && !vis[s]) {
        vis[s] = true;
        // std::queue<int> q;
        // q.push(s);
        q.push_back(s);
        int b = X[2 * ind[s]] * 4 + X[2 * ind[s] + 1] * 2;
        C[s] = b;
        // while (!q.empty()) {
        while (ii < q.size()) {
          // int node = q.front();
          // q.pop();
          int node = q[ii++];
          for (int i : bp[node]) {
            if (vis[i])
              continue;
            vis[i] = true;
            C[i] = !(C[node] - b) + b;
            // q.push(i);
            q.push_back(i);
          }
        }
      }
    }
    // int b;
    // auto dfs = [&](auto &self, int node) -> void {
    //   for (int i : bp[node]) {
    //     if (vis[i])
    //       continue;
    //     vis[i] = true;
    //     C[i] = !(C[node] - b) + b;
    //     self(self, i);
    //   }
    // };
    // for (int s = 0; s < N; ++s) {
    //   if (ind[s] != -1 && !vis[s]) {
    //     vis[s] = true;
    //     b = X[2 * ind[s]] * 4 + X[2 * ind[s] + 1] * 2;
    //     C[s] = b;
    //     dfs(dfs, s);
    //   }
    // }
  }
  for (int i = 0; i < N; ++i) {
    if (C[i] == -1) {
      for (int k = 0; k < 8; ++k) {
        bool g = true;
        for (int j : adj[i]) {
          if (C[j] == k) {
            g = false;
            break;
          }
        }
        if (g) {
          C[i] = k;
          break;
        }
      }
    }
  }
  return C;
}