#include<cstdio>
    #include<vector>
    using namespace std;
    #define MAX 8200
    #define pb push_back
    int N , M , pairs , ind , L[MAX] , R[MAX] , LS[MAX] , RS[MAX],u[MAX] ;
    bool sw;
    vector<int> G[MAX];

    void read();
    void solve();
    void write();
    bool cuplaj(int nod);
    void stingere(int nod);

    int main()
    {
        read();
        solve();
        write();
        return 0;
    }

    void read()
    {
        int x, y;
        freopen("felinare.in" , "r" , stdin );
        scanf("%d%d" , &N , &M );
        for(int i = 1 ; i <= M ; ++i )
        {
            scanf("%d%d" , &x , &y );
            G[x].pb(y);
        }
    }

    void solve()
    {
        for(sw = 1,ind = 1;sw;ind++)
        {
            sw = 0;
            for(int i = 1 ; i <= N ; ++i )
                if(!L[i] && cuplaj(i))
            {
                sw = 1;
                pairs++;
            }
        }
        for(int i = 1 ; i <= N ; ++i )
            if(L[i])LS[i] = 1;
        for(int i = 1 ; i <= N ; ++i )
            if(!LS[i])
                stingere(i);
    }

    void stingere(int nod)
    {
        for(int i = 0 ; i < (int)G[nod].size() ; ++i )
            if(!RS[G[nod][i]])
        {
            RS[G[nod][i]] = 1;
            LS[R[G[nod][i]]] = 0;
            stingere(R[G[nod][i]]);
        }
    }

    bool cuplaj(int nod)
    {
        if(u[nod] == ind)return 0;
        u[nod] = ind;
        for(int i = 0 ; i  <(int)G[nod].size() ; ++i)
            if(!R[G[nod][i]] || cuplaj(R[G[nod][i]]))
        {
            L[nod] = G[nod][i];
            R[G[nod][i]] = nod;
            return 1;
        }
        return 0;
    }

    void write()
    {
        freopen("felinare.out" , "w" , stdout );
        printf("%d\n" , 2*N-pairs);
        for(int i = 1 ; i <= N ; ++i )
            {
                int x = 1*(!LS[i])+2*(!RS[i]);
                printf("%d\n" , x);
            }
    }