#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define Nmax 20010

using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
int N,M;
int st[Nmax],dr[Nmax];
vector<int> v[Nmax];
bitset<Nmax> verif;

// st[i]=felinarul de intrare asociat felinarului de iesire i astfel incat intre ei sa existe o muchie ce intra in cuplaj
// dr[i]=felinarul de iesire asociat felinarului de intrare i astfel incat intre ei sa existe o muchie ce intra in cuplaj
// v[i]=lista felinarelor vecine felinarului i
// verif[i]=1 daca s-a incercat imperecherea felinarului i la iterarea curenta

bitset<Nmax> nu_se_aprinde;

int pairup(int);
void configure(int);

int main()
{
    f>>N>>M;
    FOR (i,1,M) {
        int x,y;
        f>>x>>y;
        v[x].pb(y+N);
    }
    bool ok=true;
    while (ok) { // algoritm de gasire a cuplajului maxim
        ok=false;
        verif.reset();
        FOR (i,1,N) {
            if (!st[i]) {
                ok |= pairup(i);
            }
        }
    }
    int nrcuplaj=0;
    FOR (i,1,N) { // initial, felinarele de iesire care intra in cuplaj nu se vor aprinde
        if (st[i]) {
            ++nrcuplaj;
            nu_se_aprinde.set(i,1);
        }
    }
    FOR (i,1,N) { // din aceasta configuratie initiala se va obtine o configuratie maxima de aprindere a felinarelor
        if (!st[i]) {
            configure(i);
        }
    }
    g<<N*2-nrcuplaj<<'\n';
    FOR (i,1,N) {
        g<<(!nu_se_aprinde.test(i+N)*2)+(!nu_se_aprinde.test(i))<<'\n';
    }
    f.close();g.close();
    return 0;
}

int pairup(int nod) {
    verif.set(nod,1);
    vector<int>::iterator it;
    for (it=v[nod].begin();it<v[nod].end();++it) {
        if (!dr[*it]) {
            st[nod]=*it;
            dr[*it]=nod;
            return 1;
        }
    }
    for (it=v[nod].begin();it<v[nod].end();++it) {
        if (!verif.test(dr[*it]) && pairup(dr[*it])) {
            st[nod]=*it;
            dr[*it]=nod;
            return 1;
        }
    }
    return 0;
}

void configure(int nod) {
    vector<int>::iterator it;
    for (it=v[nod].begin();it<v[nod].end();++it) {
        if (!nu_se_aprinde.test(*it)) {
            nu_se_aprinde.set(*it,1);
            nu_se_aprinde.set(dr[*it],0);
            configure(dr[*it]);
        }
    }
}