#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in  cin
#define out cout

using namespace std;

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

// rescriu sursa diferit pt ca n-am idee ce nu mergea

vector<int> g[8200];
int st[8200], dr[8200];
bool mr[8200];
bool scos[8200];

bool pair_up(int nod){
    if(mr[nod]) return 0;
    mr[nod] = 1;

    for(const int &cop : g[nod]){
        if(!dr[cop]){
            st[nod] = cop;
            dr[cop] = nod;
            return 1;
        }
    }

    for(const int &cop : g[nod]){
        if(pair_up(dr[cop])){
            st[nod] = cop;
            dr[cop] = nod;
            return 1;
        }
    }
    return 0;
}

void mvc(int nod){
    if(mr[nod]) return;
    mr[nod] = 1;
    for(const int &cop : g[nod]){
        if(st[nod] != cop && !scos[cop]){
            scos[cop] = 1;
            mvc(dr[cop]);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, m; in >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; in >> a >> b;
        g[a].push_back(b); 
    }

    bool mai_bine = 1;
    while(mai_bine){
        mai_bine = 0;
        for(int i = 1; i <= n; i++) mr[i] = 0;
        for(int i = 1; i <= n; i++){
            if(!st[i] && pair_up(i)){
                mai_bine = 1;
            }
        }
    }

    int cnt = 2 * n;
    for(int i = 1; i <= n; i++){
        if(st[i]) cnt--;
        else mvc(i);
    }

    out << cnt << '\n';
    for(int i = 1; i <= n; i++){
        out << mr[i] + 2 * (1 - scos[i]) << '\n';
    }

    return 0;
}