#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 <cassert>
#include <iostream>
#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> &xx = U;
      xx.clear();
      int cnt = 0;
      for (int i = 0; i < N; ++i) {
        if ((int)adj[i].size() >= 8) {
          // i = cnt;
          xx.push_back(X[2 * cnt]);
          xx.push_back(X[2 * cnt + 1]);
          cnt++;
        } else {
          xx.push_back(-1);
          xx.push_back(-1);
        }
      }
      X = xx;
    }
    std::vector<std::vector<int>> bp(N);
    for (int i = 0; i < N; ++i) {
      if ((int)adj[i].size() < 8)
        continue;
      for (int j : adj[i]) {
        if ((int)adj[j].size() < 8)
          continue;
        if (X[2 * i] != X[2 * j] || X[2 * i + 1] != X[2 * j + 1])
          continue;
        bp[i].push_back(j);
      }
    }
    std::vector<int> &vis = U;
    vis.assign(N, 0);
    C.assign(N, -1);

    std::vector<int> q;
    q.reserve(N);
    for (int s = 0; s < N; ++s) {
      if ((int)adj[s].size() >= 8 && !vis[s]) {
        vis[s] = true;
        q.push_back(s);
        int ii = 0;
        int b = X[2 * s] * 4 + X[2 * s + 1] * 2;
        C[s] = b;
        while (ii < (int)q.size()) {
          int node = q[ii++];
          for (int i : bp[node]) {
            if (vis[i])
              continue;
            vis[i] = true;
            C[i] = !(C[node] - b) + b;
            q.push_back(i);
          }
        }
      }
    }
  }
  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;
}