#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 1e4 + 5;

int A[NMax], B[NMax];
bool Used[NMax], LA[NMax], LB[NMax];

vector < int > G[NMax], v;

bool Match(const int &x){
    if(Used[x]) return 0;
    Used[x] = 1;
    for(auto it: G[x]){
        if(B[it] == 0){}
        A[x] = it; B[it] = x;
        return 1;
    }
    for(auto it: G[x]){
        if(Match(B[it])){
            A[x] = it; B[it] = x;
            return 1;
        }
    }
    return 0;
}

inline void Solve(const int &n){
    bool matching = 1;
    int ans = 0;
    while(matching){
        matching = 0;
        memset(Used, 0, sizeof(Used));
        for(int i = 1; i <= n; i++){
            if(A[i] == 0 && Match(i)){
                matching = 1;
                ans++;
            }
        }
    }
}

int main(){
    int n, m, a, b;
    fin >> n >> m;
    while(m--){
        fin >> a >> b;
        G[a].push_back(b);
    }
    Solve(n);
    bool F, S;
    int LightBulb = 0;
    for(int i = 1; i <= n; i++){
        F = S = 0;
        if(LA[i] == 0){
            F = 1;
            LB[A[i]] = 1;
        }
        if(LB[i] == 0){
            S = 1;
            LA[B[i]] = 1;
        }
        if(F == 0 && S == 0) v.push_back(0);
        if(F == 1 && S == 0) v.push_back(1), LightBulb++;
        if(F == 0 && S == 1) v.push_back(2), LightBulb++;
        if(F == 1 && S == 1) v.push_back(3), LightBulb += 2;
    }
    fout << LightBulb << "\n";
    for(auto it: v) fout << it << "\n";
    return 0;
}