#include <vector>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("felinare.in");
ofstream fout ("felinare.out");

const int Dim = 10001;

using VI = vector < int >;
using VVI = vector < VI >;

VVI G;
int n,m,R[Dim],L[Dim],maxmat,SL[Dim],SR[Dim];
bool V[Dim];

void Read();
void  HopcroftKarp();
void Suport(int node);
bool Cupleaza(int x);

int main() {

	Read();
	HopcroftKarp();
	fout << 2*n - maxmat << "\n";
    for ( int i = 1; i <= n; ++i)
        if (!SR[i])
            Suport(i);
    for ( int i = 1; i <= n; ++i)
        fout << 1 - SR[i] + 2 * ( 1 - SL[i]) << "\n";

}


void  HopcroftKarp() {

    bool found_path = true;
    while (found_path) {
        found_path = false;
        memset(V,0,sizeof(V));
        for ( int i = 1; i <= n; ++i)
            if (!L[i] and Cupleaza(i))
                ++maxmat, found_path = true;
        }
}

bool Cupleaza(int x) {

    if ( V[x] ) return false;
    V[x] = true;
    for ( const int & y : G[x])
        if (!R[y] or Cupleaza(R[y])) {
                L[x] = y;
                R[y] = x;
                SR[x] = 1;
                return true;
            }

    return false;
}

void Suport(int node) {

    for ( const int & i : G[node]) {
            if (!SL[i]) {
                SL[i] = 1;
                SR[L[i]] = 0;
                Suport(L[i]);
                }
        }
}

void Read() {

	fin >> n >> m;
	G = VVI ( n + 1 );
	int x,y;
	for ( ; m > 0; --m) {
		fin >> x >> y;
		G[x].push_back(y);
		}
}