#include <iostream>
#include <fstream>
//#include <cmath>
#include <vector>
#include <cstring>
#include <map>

using namespace std;

    int M,N;
    bool visited[302];
	int edges[302][302];
	int color[302][302];
	bool connected[302][302];
	int inputs[302*302*2];
	int col_match[302];
	bool row[302];
	int numEdges[302];
	int order[302];

	pair<int,int> edgy[302];

	void dfs(int i, bool isRow) {
		if(visited[i])return;
		visited[i] = true;
		row[i] = isRow;
		//if(isRow)fout<<"row "<<i<<endl;
		for(int j=0;j<N;j++) {
			if(connected[i][j]) {
				dfs(j,!isRow);
			}
		}

	}

	bool find_match(int id) {
     // the previous column was not matched
     if (id == -1)
       return true;
     for (int i = 0; i < N; ++ i) {
		 if(!connected[id][i])continue;
       int match = i;
       if (visited[match] == false) {
         visited[match] = true;
         if (find_match(col_match[match])) {
           col_match[match] = id;
           return true;
         }
       }
     }
     return false;
   }

	

    int main() {
		int colors = 0;
		ofstream fout ("gcoloring.out");
		ifstream fin ("gcoloring.in");
        fin>>N>>M;
		
		memset(visited,false,sizeof(visited));
		memset(row,false,sizeof(row));
		memset(edges,-1,sizeof(edges));
		memset(color,-1,sizeof(color));
		memset(connected,false,sizeof(connected));
		memset(col_match,-1,sizeof(col_match));
		memset(numEdges,0,sizeof(numEdges));

		for(int i=0;i<N;i++)order[i]=i;

		int maxK = 0;

		for(int i=0;i<M;i++) {
			int j,k;
			fin>>j;
			fin>>k;
			j--;k--;
			inputs[i*2]=j;
			inputs[i*2+1]=k;
			connected[j][k] = connected[k][j] = true;
			numEdges[j]++;
			numEdges[k]++;
			maxK = max(maxK,max(numEdges[j],numEdges[k]));
		}

		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) {
				if(numEdges[order[i]]>numEdges[order[j]]) {
					int temp = order[i];
					order[i] = order[j];
					order[j] = temp;
				}
			}
		}

		dfs(0,true);
		//for(int i=0;i<N;i++)if(row[i])fout<<"row "<<i+1<<endl;

		int matchedEdges = 0;

		while(matchedEdges < M) {
			memset(col_match,-1,sizeof(col_match));
			memset(visited,false,sizeof(visited));

			for(int i=0;i<N;i++) {
				for(int j=i+1;j<N;j++) {
					if(numEdges[order[i]]<numEdges[order[j]]) {
						int temp = order[i];
						order[i] = order[j];
						order[j] = temp;
					}
				}
			}

			int res = 0;
			for(int i=0;i<N;i++) {
				if(!row[i] && find_match(i))res++;
			}
			for(int ii=0;ii<N;ii++) {
				int i = order[ii];
				if(col_match[i]!=-1) {
					int k = col_match[i];
					connected[i][k]=false;
					connected[k][i]=false;
					edges[i][k]=colors;
					edges[k][i]=colors;
					numEdges[i]--;
					numEdges[k]--;
					//fout<<"match "<<i+1<<" "<<k+1<<endl;
				}
			}

			//fout<<res<<"res"<<endl;

			colors++;
			matchedEdges+=res;
		}

		//fout<<numEdges<<" "<<matchedEdges<<endl;

		fout<<colors<<endl;
        for(int i=0;i<M;i++) {
			fout<<edges[inputs[i*2]][inputs[i*2+1]]+1<<endl;
        }
		return 0;
	}