#include "Alice.h"
#include<cstdio>
#include<iostream>
#include<vector>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T x,Args ...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int N=2e5+7;
int deg[N];
vector<int> Alice(int n,int m,vector<int>U,vector<int>V,vector<int>c){
    vector<int> ans;
    ans.resize(n<<1);
    int cnt=0;
    for(int i=0;i<U.size();i++){
        int u=U[i],v=V[i];
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++){
        if(deg[i]<8) continue;
        if(c[i]<=1) ans[++cnt]=0,ans[++cnt]=0;
        else if(c[i]<=3) ans[++cnt]=0,ans[++cnt]=1;
        else if(c[i]<=5) ans[++cnt]=1,ans[++cnt]=0;
        else if(c[i]<=7) ans[++cnt]=1,ans[++cnt]=1;
    }
    return ans;
}

#include "Bob.h"
#include<cstdio>
#include<iostream>
#include<vector>
#define pb push_back
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T x,Args ...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int N=1e6+7;
int id[N],c[N],deg[N]; bool st[N];
vector<int>g[N];
inline void dfs(int u,int color){
    if(st[u]) return ;
    st[u]=1,c[u]=color;
    for(int v:g[u]) if(id[u]==id[v]) dfs(v,color^1);
}
vector<int> Bob(int n,int m,vector<int>U,vector<int>V,vector<int>x){
    for(int i=0;i<m;i++){
        int u=U[i]+1,v=V[i]+1;
        deg[u]++,deg[v]++;
        g[u].pb(v),g[v].pb(u);
    }
    int cnt=-1;
    for(int i=1;i<=n;i++){
        if(deg[i]<8) continue;
        id[i]=(x[++cnt]<<1)+x[++cnt]+1;
    }
    for(int i=1;i<=n;i++){
        if(!id[i]||st[i]) continue;
        dfs(i,0);
    }
    vector<int>ans;
    ans.resize(n);
    for(int i=1;i<=n;i++){
        /*if(id[i]) */ans[i-1]=(id[i]-1)*2+c[i];
//        else{
//            for(int j=0;j<8;j++) st[j]=0;
//            for(int v:g[i]) if(id[v]) st[(id[v]-1)*2+c[v]]=1;
//            for(int j=0;j<8;j++) if(!st[j]) ans[i-1]=j,c[i]=j,id[i]=1;
//        }
    }
    return ans;
}