#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=1e5+5;
int taskid, n, m, k, t;
vector<int> e[N];
namespace task1{
	int col[N];
	bool flg=0;
	inline void dfs(int x, int c){
		col[x]=c;
		for(auto y:e[x]){
			if(col[y]!=-1){
				if(col[x]==col[y]){flg=1; return ;}
			}
			else{
				dfs(y, c^1);
			}
		}
	}
	void solve(){
		memset(col, -1, sizeof col);
		for(int i=1; i<=n; ++i) if(col[i]==-1){
			dfs(i, 0);
			if(flg){
				printf("-1\n"); return ;
			}
		}
		printf("1\n");
		for(int i=1; i<=n; ++i) printf("%d ", col[i]+1);
	}
}
namespace task2{
	bool ban[N][4];
	unordered_map<int, bool> h[N];
	int que[N], hh, tt;
	int deg[N];
	vector<int> g[N];
	int col[N];
	bool ins[N];
	int bin[N], cnt, bin2[N], cnt2;
	bool suc=0;
	vector<int> e2[N];
	inline void dfs(int x){
		if(suc) return ;
		if(x==cnt+1){
			bool flg=1;
			for(int i=1; i<=cnt; ++i){
				int u=bin[i];
				for(auto v:e2[u]){
					if(col[u]==col[v]) {flg=0; break;}
				}
				if(flg==0) break;
			}
			if(flg) suc=1;
			return ;
		}
		for(int i=1; i<=3; ++i) {
			col[bin[x]]=i;
			dfs(x+1);
			if(suc) return ;
		}
	}
	int fa[N];
	inline int get(int x){
		if(x==fa[x]) return x;
		return fa[x]=get(fa[x]);
	}
	inline void merge(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return ;
		fa[x]=y;
	}
	vector<int> bel[N];
	void solve(){
		hh=1; tt=0;
		for(int i=1; i<=n; ++i) {
			for(auto j:e[i]) h[i][j]=1;
			if(e[i].size()<=2) que[++tt]=i, ins[i]=1;
		}
		while(hh<=tt){
			int x=que[hh++];
			if(h[x].size()==0) continue;
			if(h[x].size()==1){
				for(auto t:h[x]){
					int y=t.fi;
					h[y].erase(x);
					g[y].push_back(x);
					++deg[x];
					if(h[y].size()<=2&&!ins[y]) que[++tt]=y, ins[y]=1;
				}
				continue;
			}
			int y=0, z=0;
			for(auto t:h[x]){
				int v=t.fi;
				if(y==0) y=v;
				else z=v;
			}
			h[y].erase(x); h[z].erase(x);
			g[y].push_back(x); g[z].push_back(x);
			deg[x]+=2;
			if(h[y].size()<=2&&!ins[y]) que[++tt]=y, ins[y]=1;
			if(h[z].size()<=2&&!ins[z]) que[++tt]=z, ins[z]=1;
		}
		hh=1; tt=0;
		for(int i=1; i<=n; ++i) fa[i]=i;
		for(int i=1; i<=n; ++i) if(deg[i]==0) bin2[++cnt2]=i, que[++tt]=i;
		memset(ins, 0, sizeof ins);
		for(int i=1; i<=cnt2; ++i) ins[bin2[i]]=1;
		for(int i=1; i<=cnt2; ++i){
			int x=bin2[i];
			for(auto y:e[x]) if(ins[y]) e2[x].push_back(y), merge(x, y);
		}
		for(int i=1; i<=cnt2; ++i) bel[get(bin2[i])].push_back(bin2[i]);
		for(int i=1; i<=n; ++i) if(bel[i].size()){
			cnt=0;
			for(auto t:bel[i]) bin[++cnt]=t;
			dfs(1); 
			if(!suc) {
				printf("-1\n");
				return ;
			}	
		}
		while(hh<=tt){
			int x=que[hh++];
			if(col[x]==0){
				col[x]=1;
				while(ban[x][col[x]]) ++col[x];
			}
			for(auto y:g[x]){
				ban[y][col[x]]=1;
				--deg[y];
				if(deg[y]==0) que[++tt]=y;
			}
		}
		printf("1\n");
		for(int i=1; i<=n; ++i) printf("%d ", col[i]);
	}
}
int main(){
	//freopen("ex_color1.in","r",stdin);
	//freopen("ex_color1.out","w",stdout);
	read(taskid);
	read(n); read(m); read(k); read(t);
	for(int i=1, x, y; i<=m; ++i){
		read(x); read(y);
		e[x].push_back(y); e[y].push_back(x);
	}
	if(taskid==1){
		if(m!=0) printf("-1\n");
		else {
			printf("1\n");
			for(int i=1; i<=n; ++i) printf("1 ");
		}
		return 0;
	}
	if(taskid==2){
		task1::solve();
		return 0;
	}
	task2::solve();
	return 0;
}