#include <fstream>
#include <vector>

#define NLen 8192

using namespace std;

ifstream cin;
ofstream cout;

vector < int > g[NLen];

int L[NLen], R[NLen], use[NLen];
int smL[NLen], smR[NLen];

inline int cupleaza(int nod)
{
    if(use[nod]) return 0;
    use[nod] = 1;

    for(int i = 0; i < g[nod].size(); ++ i)
        if(R[ g[nod][i] ] == 0)
        {
            L[nod] = g[nod][i];
            R[ g[nod][i] ] = nod;
            smR[nod] = 1;
            return 1;
        }

    for(int i = 0; i < g[nod].size(); ++ i)
        if(R[ g[nod][i] ])
            if(cupleaza(R[ g[nod][i] ]))
            {
                L[nod] = g[nod][i];
                R[ g[nod][i] ] = nod;
                smR[nod] = 1;
                return 1;
            }

    return 0;
}

inline void verifica(int nod)
{
    for(int i = 0; i < g[nod].size(); ++ i)
        if(smR[ g[nod][i] ] == 0)
        {
            smR[ g[nod][i] ] = 1;
            smL[ L[ g[nod][i] ] ] = 0;
            verifica(L[ g[nod][i] ]);
        }
}

int main()
{
    cin.open("felinare.in");
    cout.open("felinare.out");

    int N, M;
    cin >> N >> M;

    while(M -- )
    {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
    }

    // determin cuplajul maxim

    for(int change = 1; change; )
    {
        change = 0;
        for(int i = 1; i <= N; ++ i) use[i] = 0;
        for(int i = 1; i <= N; ++ i)
            if(L[i] == 0)
                change |= cupleaza(i);
    }

    // fac suportul minim
    for(int i = 1; i <= N; ++ i)
        if( ! smR[i]) verifica(i);

    // finalizez solutia

    int num = 0;
    for(int i = 1; i <= N; ++ i)
        if(L[i]) ++ num;

    num = 2 * N - num;
    cout << num << '\n';

    for(int i = 1; i <= N; ++ i)
    {
        int bec = 0;
        if( ! smR[i]) ++ bec;
        if( ! smL[i]) bec += 2;
        cout << bec << '\n';
    }
    
    cin.close();
    cout.close();
    
    return 0;
}