#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;
	int d[N];
	
	arr Alice(int n, int m, arr u, arr v, arr c) {
		arr res;
		for (int i = 0; i < m; i++) d[u[i]]++, 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;
	int c[N];
	bitset<N> vs, vis;
	vector<int> g[N];
	
	void dfs(int u) {
		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, dfs(v);
		}
	}
	
	void bfs(int s) {
		queue<int> q; q.push(s);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			if (vis[u]) continue; vis[u] = 1;
			if (!vs[u]) {
				int tp[8]; memset(tp, 0, sizeof(tp));
				for (int v : g[u])
					if (vs[v] || vis[v]) tp[c[v]] = 1;
				for (int i = 0; i < 7; i++) if (!tp[i]) c[u] = i;
			}
			for (int v : g[u]) {
				if (vis[v]) continue;
				q.push(v);
			}
		}
	}
	
	arr Bob(int n, int m, arr u, arr v, arr x) {
		for (int i = 0; i < m; i++) {
			int x = u[i], y = v[i];
			c[x]++, c[y]++, g[x].eb(y), g[y].eb(x);
		}
		vector<int> p;
		for (int i = 0; i < n; i++) if (c[i] >= 8) p.eb(i);
		for (int i = 0; i < n; i++) c[i] = 0;
		int j = 0;
		for (int i : p) vs[i] = 1, 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++) vis[i] = 0;
		for (int i = 0; i < n; i++) if (vs[i] && !vis[i]) bfs(i);
		for (int i = 0; i < n; i++) vis[i] = 0;
		for (int i = 0; i < n; i++) if (!vs[i] && !vis[i]) bfs(i);
		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);
}