#include<bits/stdc++.h>
using namespace std;
vector<int> Alice(int n,int m,vector<int> u,vector<int> v,vector<int> c)
{
	mt19937 rng(114514);
	vector<int> vec={1,1,4,5,1,4};
	shuffle(vec.begin(),vec.end(),rng);
	return {0};
}

#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define sz(v) (int)((v).size())
#define color _color
vector<int> G[200200];
int deg[200200],vis[200200];
int color[200200],c2[200200];
void dfs(int u,int c)
{
	c2[u]=c;
	for(auto v:G[u])
		if(!vis[v]&&color[u]==color[v]&&c2[v]==-1)
			dfs(v,c^1);
}
vector<int> Bob(int n,int m,vector<int> u,vector<int> v,vector<int> x)
{
	for(int i=0;i<m;i++)
	{
		G[u[i]].pb(v[i]);
		G[v[i]].pb(u[i]);
	}
	for(int i=0;i<n;i++)
		deg[i]=sz(G[i]);
	queue<int> q;
	vector<int> order;
	for(int i=0;i<n;i++)
		if(deg[i]<8)
			q.push(i);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		order.pb(x);
		vis[x]=1;
		for(auto y:G[x])
		{
			deg[y]--;
			if(deg[y]==7)
				q.push(y);
		}
	}
	int cur=0;
	for(int i=0;i<n;i++)
		if(!vis[i])
		{
			color[i]=(x[cur]<<1)|(x[cur+1]);
			cur+=2;
		}
	memset(c2,-1,sizeof(c2));
	for(int i=0;i<n;i++)
		if(!vis[i]&&c2[i]==-1)
			dfs(i,0);
	for(int i=0;i<n;i++)
		if(!vis[i])
			color[i]=(color[i]<<1)|c2[i];
	reverse(order.begin(),order.end());
	for(auto x:order)
	{
		vis[x]=0;
		int vis[8]={0,0,0,0,0,0,0,0};
		for(auto y:G[x])
			if(!vis[y])
				vis[color[y]]=1;
		while(vis[color[x]])
			color[x]++;
	}
	vector<int> ret(n);
	for(int i=0;i<n;i++)
		ret[i]=color[i];
	return ret;
}