#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;

// #define int long long
const int MAXN = 2e5 + 5;

int deg[MAXN];

vector<int> Alice(int n, int m, vector<int> U, vector<int> V, vector<int> c) {
	vector<int> ret;

	for(int i = 0; i < m; ++i) {
		++deg[U[i] + 1]; ++deg[V[i] + 1];
	}

	int cnt = 0;
	for(int i = 1; i <= n; ++i) {
		if(deg[i] < 8) continue;
		++cnt;
	}
	ret.resize(2 * cnt);

	cnt = 0;
	for(int i = 1; i <= n; ++i) {
		if(deg[i] < 8) continue;

		if(c[i - 1] <= 1) {
			ret[cnt] = 0; ret[cnt + 1] = 0;
		}
		else if(c[i - 1] <= 3) {
			ret[cnt] = 0; ret[cnt + 1] = 1;
		}
		else if(c[i - 1] <= 5) {
			ret[cnt] = 1; ret[cnt + 1] = 0;
		}
		else if(c[i - 1] <= 7) {
			ret[cnt] = 1; ret[cnt + 1] = 1;
		}
		cnt += 2;
	}

	return ret;
}

#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;

// #define int long long
const int MAXN = 2e5 + 5;

int val[MAXN], color[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
// vector<bool> temp;

void dfs(int u, bool c) {
	if(vis[u]) return;
	vis[u] = true;
	color[u] = (c ? 1 : 0);

	for(auto v : adj[u]) {
		if(val[u] == val[v]) dfs(v, c ^ 1);
	}
}

vector<int> Bob(int n, int m, vector<int> U, vector<int> V, vector<int> x) {
	for(int i = 0; i < m; ++i) {
		int a = U[i] + 1, b = V[i] + 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}

	int idx = 0;
	for(int i = 1; i <= n; ++i) {
		if(adj[i].size() < 8) continue;

		val[i] = (2 * x[idx++]) + (x[idx++] + 1);
	}

	for(int i = 1; i <= n; ++i) {
		if(val[i] == 0 || vis[i]) continue;
		dfs(i, 0);
	}

	vector<int> ans; ans.resize(n);
	for(int i = 1; i <= n; ++i) {
		if(val[i] == 0) {
			// temp.clear();
			for(int j = 0; j < 8; ++j) vis[j] = false;

			for(auto v : adj[i]) {
				if(val[v]) {
					vis[2 * (val[v] - 1) + color[v]] = true;
				}
			}

			for(int j = 0; j < 8; ++j) {
				if(vis[j]) continue;
				ans[i - 1] = j;
				color[i] = j;
				val[i] = 1;
			}
		}
		else {
			ans[i - 1] = 2 * (val[i] - 1) + color[i];
		}
	}

	return ans;
}