#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N = 4e5+5;
int n,m;
int in[N],col[N];
vector<int>ed[N];
int gcd(int a,int b){
	return !b?a:gcd(b,a%b);
}
void rs(int u){
	int sz = ed[u].size();
	for(int i=0;i<sz;i++){
		int x = ed[u][i];
		if(col[x]){
			continue;
		}
		col[x] = col[u]*-1;
		rs(x);
	}
} 
struct aa{
	int id,x,y;
}E[N],S[N],E1[N],E2[N];//S不变，E分治 
struct bb{
	int id,nxt;
}e[N*2];
int cnt,tote,tot1,tot2;
int head[N];bool vis[N];
void link(int u,int i){
	e[++tote] = (bb){i,head[u]};head[u] = tote;
//	cout<<"TOT:"<<u<<" "<<tote<<"\n"; 
}
void oula(int u){
//	cout<<"U:"<<u<<" "<<head[u]<<"\n"; 
	for(int &i=head[u];i;i=e[i].nxt){
//		head[u] = i; 
		aa x = S[e[i].id];
		if(vis[x.id]){
			continue;
		}
		vis[x.id] = 1;
		if(col[u]==1){
			E1[++tot1] = x;
		}else{
			E2[++tot2] = x;
		}
		if(x.x==u){
			oula(x.y);
		}else{
			oula(x.x);
		}
	}
}
int ans[N];
void sol(int k,int l,int r){
//	cout<<"K:"<<k<<" "<<l<<" "<<r<<"\n"; 
	if(!k){
		cnt++;
		for(int i=l;i<=r;i++){
			ans[E[i].id] = cnt;
		}
		return;
	}
	for(int i=l;i<=r;i++){
		head[E[i].x] = head[E[i].y] = 0;
	}
	tote = 0;
	for(int i=l;i<=r;i++){
		link(E[i].x,E[i].id);link(E[i].y,E[i].id);
	}
	tot1 = tot2 = 0;
//	cout<<"there\n"; 
	for(int i=l;i<=r;i++){
		oula(E[i].x);
		oula(E[i].y);
	}
//	cout<<"hrere\n"; 
	for(int i=l;i<=r;i++){
		vis[E[i].id] = 0;
	}
	int mid = (l+r)/2;
	for(int i=l;i<=mid;i++){
		E[i] = E1[i-l+1];
	}
	for(int i=mid+1;i<=r;i++){
		E[i] = E2[i-mid];
	}
	sol(k-1,l,mid);sol(k-1,mid+1,r);
}
void init(){
	for(int i=1;i<=n;i++){
		in[i] = 0;
		ed[i].clear();
		col[i] = 0;
	}
	cnt = 0; 
	for(int i=1;i<=m;i++){
		int x,y;
		x = read();y = read();
		in[x]++;in[y]++;E[i] = (aa){i,x,y};S[i] = E[i];
		ed[x].push_back(y);ed[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if((in[i]&1)||(!in[i])){
			cout<<-1<<"\n";
			return;
		}
		if(!col[i]){
			col[i] = 1;
			rs(i);
		}
	}
	int now = 0;
	for(int i=1;i<=n;i++){
		now = gcd(now,in[i]);
	} 
	int k = 0;
	while(now%2==0){
		k++;now>>=1;
	}
	cout<<k<<"\n";
	sol(k,1,m);
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
	
}
int main(){
//	freopen("ex_coloring1.in","r",stdin);
//	freopen("me.txt","w",stdout); 
	while(1){
		n = read();m = read();
		if(n==0&&m==0){
			break;
		} 
//		cout<<1<<"\n"; 
		init();
//		cout<<2<<"\n";
	}
	return 0;
}