# include <fstream>
 # include <vector>
 # include <algorithm>
 
 # define pb push_back
 
 # define dim 8200
 # define inf 9999999
 
 using namespace std;
 
 ifstream f("felinare.in");
 ofstream g("felinare.out");
 
 vector < int > a[ dim ];
 
 struct felinar
 {
	 int st, dr;
 };
 
 felinar sol[ dim ];
 
 int l[ dim ], r[ dim ], uz[ dim ];
 int nrfelinare;
 int n, m;
 
 int calculeaza( int n )
 {
	 int i;
	 if ( uz[ n ] == 1 )
		 return 0;
	 
	 uz[ n ] = 1;
	 
	 for ( i = 0 ; i < a[ n ].size() ; i++ )
		 if( r[ a[ n ][ i ] ] == 0 )
		 {
			 l[ n ] = a[ n ][ i ];
			 r[ a[ n ][ i ] ] = n;
			 return 1;
		 }
		 
		 for ( i = 0 ; i < a[ n ].size() ; i++ )
			 if ( calculeaza( r[ a[ n ][ i ] ] ) == 1 )
			 {
				 r[ a[ n ][ i ] ] = n;
				 l[ n ] = a[ n ][ i ];
				 return 1;
			 }
			 
			 return 0;
 }
 
 void citire()
 {
	 int i, x, y, j;
	 
	 f >> n >> m;
	 
	 for ( i = 1 ; i <= n ;i ++ )
	 {
		 f >> x >> y;
		 a[ x ].pb( y );
	 }
	
 }
 void rezolva()
 {
	 int i, j, schimba = 1; 
	 
	 schimba = 1;
	 
	 while ( schimba )
	 {
		 schimba = 0;
		 
		 for ( j = 1 ; j <= n ; j++ )
			 uz[ i ] = 0;
		 
		 for ( i = 1 ; i <= n ; i++ )
			 if ( l[ i ] == 0 )
				 if ( calculeaza( i ) == 1 )
					 schimba = 1;
	 }
	 
	 for ( i = 1 ; i <= n ; i++ )
	 {
		 if ( l[ i ] != 0 )
		 {
			 sol[ i ].st = 1;
			 sol[ l[ i ] ].dr = - 1;
		 }
		 else
		 {
			 sol[ i ].st = 1;
			 sol[ i ].dr = 1;
		 }
	 }
	 
	 for ( i = 1 ; i <= n ; i++ )
	 {
		 if ( sol[ i ].st == 1 && sol[ i ].dr == 1 )
			 nrfelinare = nrfelinare + 2;
		 else
		 if( sol[ i ].st == 1 || sol[ i ].dr == 1 )
			 nrfelinare ++;
	 }
 }
 
 void afisare()
 {
	 int i, j;
	 g << nrfelinare << "\n";
	 for ( i = 1 ; i <= n ; i++ )
		 if ( sol[ i ].st == 1 && sol[ i ].dr != 1 )
			 g << 1 << "\n";
		 else
			 if ( sol [ i ].st != 1 && sol[ i ].dr == 1 )
				 g << 2 << "\n";
			 else
				 if ( sol[ i ].st == 1 && sol[ i ].dr == 1 )
					 g << 3 << "\n";
				 else
					 g << 0 << "\n";
		 
		 //if ( sol[ i ].st == 1 )
		 //g << sol[ i ].st << " " << sol[ i ].dr << "\n";
 }
 int main()
 {
	 citire();
	 rezolva();
	 afisare();
	 return 0;
 }