#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

const int N_MAX = 8200;
const int M_MAX = 20005;

int n;
vector<vector<int>> G;

int L[N_MAX], R[N_MAX];
bitset<N_MAX> l_choose,
              r_choose;

void read_graph(){
    ifstream fin("felinare.in");
    int m;
    fin >> n >> m;
    G.resize(n + 1);
    while(m--){
        int x, y; fin >> x >> y;
        G[x].push_back(y);
        //G[2 * y + 1].push_back(2 * x);
    }
    fin.close();
}

bitset<N_MAX> seen;

bool matched(int u){
    if(seen[u]) return 0;
    seen[u] = 1;
    for(int& v: G[u]){
        if(!R[v]){
            R[v] = u;
            L[u] = v;
            return 1;
        }
    }
    for(int& v: G[u]){
        if(matched(R[v])){
            R[v] = u;
            L[u] = v;
            return 1;
        }
    }
    return 0;
}

void hopcroft_karp(){
    int wasChanged = 1;
    int i;
    while(wasChanged){
        wasChanged = 0;
        seen.reset();
        for(int i = 1; i <= n; i++)
            if(!L[i] && matched(i))
                wasChanged = 1;
    }
}

void support(int u){
    for(int& v: G[u]){
        if(!r_choose[v]){
            r_choose[v] = 1;
            l_choose[R[v]] = 0;
            support(R[v]);
        }
    }
}

void compute_min_support(){
    for(int i = 1; i <= n; i++)
        if(L[i]) l_choose[i] = 1;
    for(int i = 1; i <= n; i++)
        if(!L[i]) support(i);
}

void flip_choosings(){
    l_choose.flip();
    r_choose.flip();
}

void print_answers(){
    ofstream fout("felinare.out");
    int lights = 0;
    for(int i = 1; i <= n; i++){
        lights += l_choose[i];
        lights += r_choose[i];
    }
    fout << lights << '\n';
    for(int i = 1; i <= n; i++) 
        fout << l_choose[i] + 2 * r_choose[i] << '\n';
    fout.close();
}

int main(){
    read_graph();
    hopcroft_karp();
    compute_min_support();
    flip_choosings();
    print_answers();
    return 0;
}