#include <fstream>
#include <vector>
using namespace std;

const int maxn=8192;

int n, m, k, is_l[maxn], is_r[maxn], viz[maxn], cnt[maxn], st[maxn], dr[maxn];
vector<int> L[maxn];

bool cupleaza(int x){
    if(viz[x]==k)
			return 0;
    viz[x]=k;

    for(auto y: L[x])
			if(!dr[y]){
        st[x]=y;
        dr[y]=x;
        return 1;
			}

    for(auto y: L[x])
			if(cupleaza(dr[y])){
        st[x] = y;
        dr[y] = x;
        return 1;
			}

    return 0;
}

void DFS(int x){
    for(auto y: L[x])
			if(!is_r[y]){
        is_r[y]=1;
        DFS(dr[y]);
			}
}

int main(){
		ifstream fin ("felinare.in");
    int i, A, B, gata, res=0;

		fin >> n >> m;
    for(i=1; i<=m; i++){
				fin >> A >> B;
        L[A].push_back(B);
    }
		fin.close();

    gata = 1;
    while(gata){
        k++;
        gata = 0;
        for(i=1; i<=n; i++)
					if(!st[i] && cupleaza(i))
						res++, gata=1;
    }

		ofstream fout ("felinare.out");
    fout << 2*n-res << '\n';

    for(i=1; i<=n; i++)
			viz[i]=0;

    for(i=1; i<=n; i++)
			if(!st[i])
				DFS(i);

    for(i=1; i<=n; i++)
			if(st[i] && !is_r[ st[i] ])
				is_l[i] = 1;

    for(i=1; i<=n; ++i){
        if(is_l[i] && is_r[i])
					fout << "0\n";
        else if(is_r[i])
					fout << "1\n";
        else if(is_l[i])
					fout << "2\n";
        else
					fout << "3\n";
    }
		fout.close();

	return 0;
}