#include "Bob"
#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> arr;
namespace B {
const int N = 2e5;
const int M = 5e5 + 5;
vector<char> c;
vector<bool> vis;
int hd[N], d[N], tot;
struct E {
int to, nxt;
} e[M << 1];
int vs(int u) {
return d[u] >= 8;
}
void bfs(int u) {
queue<int> q; q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 1;
for (int i = hd[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!vs(v) || vis[v] || (c[u] >> 1) != (c[v] >> 1)) {
continue;
}
c[v] = c[u] ^ 1, vis[v] = 1, q.push(v);
}
}
}
void add(int u, int v) {
d[u]++, e[++tot] = (E) { v, hd[u] }, hd[u] = tot;
}
arr Bob(int n, int m, arr u, arr v, arr x) {
vis.resize(n), c.resize(n);
for (int i = 0; i < m; i++) {
add(u[i], v[i]);
add(v[i], u[i]);
}
vector<int> p;
for (int i = 0; i < n; i++) {
if (vs(i)) {
p.eb(i);
}
}
int j = 0;
for (int i : p) {
c[i] = (x[j] << 1) | (x[j + 1] << 2);
j += 2;
}
for (int i = 0; i < n; i++) {
if (vs(i) && !vis[i]) {
bfs(i);
}
}
for (int i = 0; i < n; i++) {
if (vs(i)) continue;
int tp = 0;
for (int j = hd[i]; j; j = e[j].nxt) {
int v = e[j].to;
if (vs(v) || v < i) {
tp |= (1 << c[v]);
}
}
for (int j = 0; j < 8; j++) {
if (((tp >> j) & 1) ^ 1) {
c[i] = j;
}
}
}
arr res;
for (int i = 0; i < n; i++) {
res.eb(c[i]);
}
return res;
}
}
arr Bob(int n, int m, arr u, arr v, arr x) {
return B::Bob(n, m, u, v, x);
}