#include <bits/stdc++.h>
#include "Alice.h"

const int MX = 2e5 + 10;

int deg[MX];

std::vector <int> Alice(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> C) {
	for(int i = 0; i < M; ++i) ++deg[U[i]], ++deg[V[i]];
	std::vector <int> ret;
	for(int i = 0; i < N; ++i) if(deg[i] >= 8) ret.push_back(C[i] >> 2 & 1), ret.push_back(C[i] >> 1 & 1);
	return ret;
}

#include <bits/stdc++.h>
#include "Bob.h"

const int MX = 2e5 + 10;

std::vector <int> G[MX];
int n, m, bl[MX], col[MX], deg[MX];

void bfs(int S, int c){
	std::queue <int> q;
	q.push(S), col[S] = 2 * c;
	while(q.size()){
		int x = q.front(); q.pop();
		for(auto y : G[x]) if(bl[y] == c && col[y] == -1) col[y] = col[x] ^ 1, q.push(y);
	}
}

void paint(int c){
	for(int i = 0; i < n; ++i) if(bl[i] == c && col[i] == -1) bfs(i, c);
}

std::vector <int> Bob(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> X) {
	n = N, m = M;
	for(int i = 0; i < m; ++i){
		G[U[i]].push_back(V[i]), G[V[i]].push_back(U[i]);
		++deg[U[i]], ++deg[V[i]];
	}
	for(int i = 0; i < n; ++i) bl[i] = -1, col[i] = -1;
	int cur = 0, sizx = X.size();
	for(int i = 0; i < sizx; i += 2){
		while(cur < N - 1 && deg[cur] < 8) ++cur;
		bl[cur] = 2 * X[i] + X[i + 1];
	}
	for(int i = 0; i < 4; ++i) paint(i);
	for(int i = 0; i < n; ++i){
		if(deg[i] >= 8) continue;
		static bool vis[8];
		memset(vis, 0, sizeof vis);
		for(auto y : G[i]) if(col[y] != -1) vis[col[y]] = 1;
		for(int j = 0; j < 8; ++j) if(!vis[j]){
			col[i] = j;
			break;
		}
	}
	std::vector <int> ret;
	for(int i = 0; i < n; ++i) ret.push_back(col[i]);
	return ret;
}