#include "Alice.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace {
using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")



// remove deg < 8
pair<vector<int>, vector<int>> removeEasy(int N, int M, const vector<int> &U, const vector<int> &V) {
  vector<vector<int>> graph(N);
  for (int i = 0; i < M; ++i) {
    graph[U[i]].push_back(V[i]);
    graph[V[i]].push_back(U[i]);
  }
  vector<int> deg(N);
  vector<int> us;
  for (int u = 0; u < N; ++u) {
    deg[u] = graph[u].size();
    if (deg[u] < 8) {
      us.push_back(u);
    }
  }
  for (int j = 0; j < (int)us.size(); ++j) {
    const int u = us[j];
    for (const int v : graph[u]) {
      if (deg[v]-- == 8) {
        us.push_back(v);
      }
    }
  }
  vector<int> del(N, 0);
  for (const int u : us) del[u] = 1;
  vector<int> vs;
  for (int v = 0; v < N; ++v) if (!del[v]) vs.push_back(v);
  return make_pair(us, vs);
}
}  // namespace

std::vector <int> Alice(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> C) {
  const auto res = removeEasy(N, M, U, V);
// cerr<<"res = "<<res<<endl;
  /*
    remaining graph
      deg(v) >= 8
      ==> |vs| <= (1/4) M
  */
  vector<int> X;
  for (const int v : res.second) {
    X.push_back(C[v] >> 1 & 1);
    X.push_back(C[v] >> 2 & 1);
  }
  return X;
}

#include "Bob.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace {
using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


vector<int> uf;
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}

// remove deg < 8
pair<vector<int>, vector<int>> removeEasy(int N, int M, const vector<int> &U, const vector<int> &V) {
  vector<vector<int>> graph(N);
  for (int i = 0; i < M; ++i) {
    graph[U[i]].push_back(V[i]);
    graph[V[i]].push_back(U[i]);
  }
  vector<int> deg(N);
  vector<int> us;
  for (int u = 0; u < N; ++u) {
    deg[u] = graph[u].size();
    if (deg[u] < 8) {
      us.push_back(u);
    }
  }
  for (int j = 0; j < (int)us.size(); ++j) {
    const int u = us[j];
    for (const int v : graph[u]) {
      if (deg[v]-- == 8) {
        us.push_back(v);
      }
    }
  }
  vector<int> del(N, 0);
  for (const int u : us) del[u] = 1;
  vector<int> vs;
  for (int v = 0; v < N; ++v) if (!del[v]) vs.push_back(v);
  return make_pair(us, vs);
}
}  // namespace

std::vector <int> Bob(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> X) {
  const auto res = removeEasy(N, M, U, V);
  const auto &us = res.first, &vs = res.second;
  vector<int> C(N, -1);
  for (const int v : vs) C[v] = -2;
  vector<int> uf(N << 1, -1);
  for (int i = 0; i < M; ++i) if (C[U[i]] == -2 && C[V[i]] == -2) {
    connect(U[i] << 1, V[i] << 1 | 1);
    connect(V[i] << 1, U[i] << 1 | 1);
  }
  vector<int> colors(N << 1, -1);
  {
    int pos = 0;
    for (const int v : vs) {
      const int r = root(v << 1);
      if (!~colors[r]) {
        colors[r] = 0;
        colors[root(r ^ 1)] = 1;
      }
      C[v] = colors[r];
      C[v] |= X[pos++] << 1;
      C[v] |= X[pos++] << 2;
    }
  }
  vector<vector<int>> graph(N);
  for (int i = 0; i < M; ++i) {
    graph[U[i]].push_back(V[i]);
    graph[V[i]].push_back(U[i]);
  }
  for (int j = (int)us.size(); --j >= 0; ) {
    const int u = us[j];
    int app = 0;
    for (const int v : graph[u]) if (~C[v]) app |= 1 << C[v];
    C[u] = __builtin_ctz(~app);
  }
  return C;
}