#include <stdio.h>
#include <vector>
#define N1 (8191 * 2)
#define N2 20000

std::vector <int> g[1 + N1], reverse_g[1 + N2];
int cuplat_1[1 + N1], cuplat_2[1 + N2];
bool parcurs[1 + N2];
int n1, n2;

bool exista_drum(int node) {
    for ( int vecin : g[node] ) {
        if ( !parcurs[vecin] ) {
            parcurs[vecin] = true;
            if ( !cuplat_2[vecin] ) {
                cuplat_1[node] = vecin;
                cuplat_2[vecin] = node;
                return true;
            }
            if ( exista_drum(cuplat_2[vecin]) ) {
                cuplat_1[node] = vecin;
                cuplat_2[vecin] = node;
                return true;
            }
        }
    }
    return false;
}

int main() {
    FILE *fin, *fout;
    int x, y;

    fin = fopen("felinare.in", "r");
    fscanf(fin, "%d%d", &n1, &n2);
    for ( int i = 1; i <= n2; i ++ ) {
        fscanf(fin, "%d%d", &x, &y);
        g[x * 2 - 1].push_back(i);
        g[y * 2].push_back(i);

        reverse_g[i].push_back(x * 2 - 1);
        reverse_g[i].push_back(y * 2);
    }
    fclose(fin);

    bool ok = true;
    while ( ok ) {
        ok = false;
        for ( int i = 1; i <= n2; i ++ )
            parcurs[i] = false;
        for ( int i = 1; i <= n1 * 2; i ++ )
            if ( !cuplat_1[i] && exista_drum(i) )
                ok = true;
    }

    for ( int i = 1; i <= n1 * 2; i ++ ) {
        if ( cuplat_1[i] ) {
            for ( int vecin : reverse_g[cuplat_1[i]] ) {
                if ( vecin != i ) {
                    cuplat_1[vecin] = 0;
                }
            }
        }
    }

    int nr_fel = 0;
    for ( int i = 1; i <= n1 * 2; i ++ )
        if ( cuplat_1[i] || !g[i].size() )
            nr_fel ++;

    fout = fopen("felinare.out", "w");
    fprintf(fout, "%d\n", nr_fel);
    for ( int i = 1; i <= n1 * 2 - 1; i += 2 ) {
        int cnt = 0;
        if ( cuplat_1[i] || !g[i].size() )
            cnt ++;
        if ( cuplat_1[i + 1] || !g[i + 1].size() )
            cnt += 2;
        fprintf(fout, "%d\n", cnt);
    }
    fclose(fout);
    return 0;
}