#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
const int B=8;
namespace {
	const int N=2e5+5;
	vector <int> G[N];
	int in[N];
	queue <int> q;
	
	vector <int> ANS;
}

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++){
		int u=U[i]+1,v=V[i]+1;
		G[u].push_back(v),G[v].push_back(u);
		in[u]++,in[v]++;
	}
	for(int i=1;i<=n;i++){
		if(in[i]<B) q.push(i);
	}
	while(q.size()){
		int u=q.front(); q.pop();
		for(int v: G[u]){
			if(in[v]<B) continue;
			in[v]--;
			if(in[v]<B) q.push(v);
		}
	}
	
	for(int i=1;i<=n;i++){
		if(in[i]>=B){
			for(int t=0;t<2;t++) ANS.push_back(C[i-1]>>t & 1);
		}
	}
	ANS.push_back(0);
//	cout<<"Alice send: ";
//	for(int x: ANS) cout<<x<<" ";
//	cout<<'\n';
	return ANS;
}

#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
const int B=8;
namespace {
	const int N=2e5+5;
	vector <int> G[N];
	int in[N];
	queue <int> q;
	
	stack <int> sta;
	int col[N];
	
	bool vis[N];
	void dfs(int u,int c){
		if(col[u]==-1 || vis[u]) return ;
		vis[u]=1;
		col[u] |= c<<2;
		for(int v: G[u]){
			dfs(v,c^1);
		}
	}
	
	
	vector <int> ANS;
}

std::vector <int> Bob(int n, int m, std::vector <int> U, std::vector <int> V, std::vector <int> X) {
	for(int i=0;i<m;i++){
		int u=U[i]+1,v=V[i]+1;
		G[u].push_back(v),G[v].push_back(u);
		in[u]++,in[v]++;
	}
	for(int i=1;i<=n;i++){
		if(in[i]<B) q.push(i),sta.push(i);
	}
	while(q.size()){
		int u=q.front(); q.pop();
		for(int v: G[u]){
			if(in[v]<B) continue;
			in[v]--;
			if(in[v]<B) q.push(v),sta.push(v);
		}
	}
	int nw=0;
	for(int i=1;i<=n;i++){
		if(in[i]>=B){
			for(int t=0;t<2;t++) col[i] |= X[nw]<<t,nw++;
		}
		else col[i]=-1;
	}
	
	for(int i=1;i<=n;i++) dfs(i,0);
	
	while(sta.size()){
		int u=sta.top(); sta.pop();
		bool buc[B]={};
		for(int v: G[u])
			if(col[v]>=0) buc[col[v]]=1;
		int nw=0;
		while(buc[nw]) nw++;
		col[u]=nw;
	}
	for(int i=1;i<=n;i++) ANS.push_back(col[i]);
//	cout<<"Bob send: ";
//	for(int x: ANS) cout<<x<<" ";
//	cout<<'\n';
	return ANS;
}