#include<bits/stdc++.h>
#include "Alice.h"
using namespace std;
vector<int> deg,res;
std::vector<int> Alice(int N,int M,std::vector<int> U,std::vector<int> V,std::vector<int> C){
	deg.resize(N);
	for(int i=0;i<M;i++) deg[U[i]]++,deg[V[i]]++;
	for(int i=0;i<N;i++) 
		if(deg[i]==8) res.emplace_back(C[i]&1),res.emplace_back(C[i]>>1&1);
	return res;
}

#include<bits/stdc++.h>
#include "Bob.h"
using namespace std;
vector<int> g[200005],col,tmp[4],vis;
inline void dfs(int x,int c){
	col[x]=c;
	for(auto v:g[x])
		if(!col[v]&&vis[v]) dfs(v,3-c); 
}
std::vector<int> Bob(int N,int M,std::vector<int> U,std::vector<int> V,std::vector<int> X){
	col.resize(N),vis.resize(N);
	for(int i=0;i<M;i++) g[U[i]].emplace_back(V[i]),g[V[i]].emplace_back(U[i]);
	for(int i=0,j=0;i<N;i++){
		if(g[i].size()<8) continue;
		tmp[X[j]<<1|X[j+1]].emplace_back(i),j+=2;
	}
	for(int k=0;k<4;k++){
		vis.clear();
		for(auto v:tmp[k]) vis[v]=1;
		for(auto v:tmp[k])
			if(!col[v]) dfs(v,1);
		for(auto v:tmp[k]) col[v]+=k+k; 
	} 
	for(int i=0;i<N;i++){
		if(g[i].size()==8) continue; 
		vector<int> now;
		for(auto v:g[i]) 
			if(col[v]) now.emplace_back(col[v]);
		sort(now.begin(),now.end()),now.erase(unique(now.begin(),now.end()),now.end());
		for(int j=0;j<now.size();j++){
			if(now[j]!=j+1){
				col[i]=j+1;
				break;
			}
		}
		if(!col[i]) col[i]=now.size()+1;
	}
	for(int i=0;i<N;i++) col[i]--;
	return col;
}