/*
ID: espr1t
LANG: C++
TASK: Demo
KEYWORDS: 
*/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <queue>
#include <map>
#include <set>

#define MAX 302

using namespace std;
FILE *in; FILE *out;

int n, m;
int numColors, nextNode;
int color[MAX * MAX], parity[MAX];
vector <int> index[MAX], v[MAX];
int used[MAX][MAX];


void getParity(int node, int par)
{
	parity[node] = par;
	for (int i = 0; i < (int)v[node].size(); i++)
		if (parity[v[node][i]] == -1) getParity(v[node][i], !par); 
}


int main(void)
{
	in = stdin; out = stdout;
	in = fopen("gcoloring.in", "rt"); out = fopen("gcoloring.out", "wt");
	
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int node1, node2;
		fscanf(in, "%d %d", &node1, &node2);
		v[node1].push_back(node2); index[node1].push_back(i);
		v[node2].push_back(node1); index[node2].push_back(i);
	}
	memset(color, -1, sizeof(color));
	
	numColors = 0;
	for (int i = 1; i <= n; i++)
		numColors = max(numColors, (int)v[i].size());
	
	memset(parity, -1, sizeof(parity));
	for (int i = 1; i <= n; i++)
		if (parity[i] == -1) getParity(i, 0);
	
	bool found = false;
	while (!found)
	{
		vector < vector <int> > ass;
		ass.push_back(vector <int>());
		for (int i = 1; i <= n; i++)
		{
			vector <int> add;
			for (int c = 0; c < numColors; c++)
				add.push_back(c);
			random_shuffle(add.begin(), add.end());
			ass.push_back(add);
		}

		found = true;
		memset(used, 0, sizeof(used));
		for (int i = 1; i <= n; i++) if (parity[i] == 0)
		{
			int tused[MAX];
			memset(tused, 0, sizeof(tused));
			
			int cflag = 1;
			for (int c = 0; c < (int)v[i].size(); c++)
			{
				int fnd = 0;
				for (int j = 0; j < (int)ass[i].size(); j++)
				{
					if (!tused[j] && !used[v[i][c]][ass[i][j]])
					{
						tused[j] = 1;
						used[v[i][c]][ass[i][j]] = 1;
						color[index[i][c]] = ass[i][j];
						fnd = 1; break;
					}
				}
				if (!fnd) {cflag = 0; break;}
			}
			if (!cflag) {found = false; break;}
		}
	}
	fprintf(out, "%d\n", numColors);
	for (int i = 0; i < m; i++)
		fprintf(out, "%d\n", color[i] + 1);
	return 0;
}