#include "Alice.h"
#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 A {
	const int N = 2e5 + 5;
	vector<char> d;
	
	arr Alice(int n, int m, arr u, arr v, arr c) {
		d.resize(n);
		arr res;
		for (int i = 0; i < m; i++) {
			if (d[u[i]] < 8) d[u[i]]++;
			if (d[v[i]] < 8) d[v[i]]++;
		}
		for (int i = 0; i < n; i++) if (d[i] >= 8) res.eb((c[i] >> 1) & 1), res.eb(c[i] >> 2);
		return res;
	}
}

arr Alice(int n, int m, arr u, arr v, arr c) {
	return A::Alice(n, m, u, v, c);
}

#include "Bob.h"
#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 tuple<int, int, int> tu;
typedef vector<int> arr;

namespace B {
	const int N = 2e5 + 5;
	vector<char> c;
	bitset<N> vis;
	vector<vector<int> > g;
	
	int vs(int u) {
		return (int)g[u].size() >= 8;
	}
	
	void dfs(int u) {
		queue<int> q; q.push(u);
		while (!q.empty()) {
			int u = q.front(); q.pop(), vis[u] = 1;
			for (int v : g[u]) {
				if (!vs(v) || vis[v] || (c[u] >> 1) != (c[v] >> 1)) continue;
				c[v] = c[u] ^ 1, q.push(v);
			}
		}
	}
	
	arr Bob(int n, int m, arr u, arr v, arr x) {
		c.resize(n), g.resize(n);
		for (int i = 0; i < m; i++) {
			int x = u[i], y = v[i];
			g[x].eb(y), g[y].eb(x);
		}
		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]) dfs(i);
		for (int i = 0; i < n; i++) {
			if (vs(i)) continue;
			int tp = 0;
			for (int v : g[i]) 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);
}