#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

namespace
{

int deg[200005];
bool vis[200005];
vector<int> g[200005];

} // anonymous namespace

vector<int> Alice(int N,int M,vector<int> U,vector<int> V,vector<int> C)
{
	for(int i=0,u,v;i<M;i++)
	{
		u=U[i],v=V[i],deg[u]++,deg[v]++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	queue<int> q;
	for(int i=0;i<N;i++) if(deg[i]<8) q.push(i),vis[i]=true;
	while(!q.empty())
	{
		int u=q.front();
		for(auto &v: g[u])
			if(!vis[v] && (--deg[v])<8)
				q.push(v),vis[v]=true;
		q.pop();
	}
	vector<int> res;
	for(int i=0;i<N;i++)
	{
		if(vis[i]) continue;
		res.push_back(C[i]&1);
		res.push_back(C[i]>>1&1);
	}
	return res;
}

#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;

namespace
{

int t,deg[200005],col[200005],id[200005];
bool vis[200005];
vector<int> g[200005];

} // anonymous namespace

vector<int> Bob(int N,int M,vector<int> U,vector<int> V,vector<int> X)
{
	for(int i=0,u,v;i<M;i++)
	{
		u=U[i],v=V[i],deg[u]++,deg[v]++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	queue<int> q;
	for(int i=0;i<N;i++) if(deg[i]<8) q.push(i),vis[i]=true;
	vector<int> ord,ans(N);
	while(!q.empty())
	{
		int u=q.front();
		for(auto &v: g[u])
			if(!vis[v] && (--deg[v])<8)
				q.push(v),vis[v]=true;
		ord.push_back(u),q.pop();
	}
	for(int i=0;i<N;i++) if(!vis[i]) id[i]=t++;
	for(int i=0;i<t;i++) X[i]=X[i<<1]|(X[i<<1|1]<<1);
	fill(col,col+N,-1);
	function<void(int,int)> dfs=[&dfs,&X,&ans](int u,int c)
	{
		if(~col[u]) return;
		col[u]=c,ans[u]=X[id[u]]|(col[u]<<2);
		for(auto &v: g[u])
		{
			if(X[u]!=X[v]) continue;
			if(~col[v]) dfs(v,!c);
		}
	};
	for(int i=0;i<N;i++) dfs(i,0);
	reverse(ord.begin(),ord.end());
	for(auto &u: ord)
	{
		bool has[8]={false};
		for(auto &v: g[u])
		{
			if(vis[v]) continue;
			has[ans[v]]=true;
		}
		while(has[ans[u]]) ans[u]++;
		vis[u]=false;
	}
	return ans;
}