#include <cstring>

#include <fstream>
#include <vector>
using namespace std;

const int N=8192;
int S[N],D[N],n,nr;
vector<int> a[N];
bool use[N],st[N],dr[N];

ifstream in("felinare.in");
ofstream out("felinare.out");

bool pairup(int x)
{
    if (use[x]) return false;
    use[x] = true;

    for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
        if (!D[*i] || pairup(D[*i]))
        {
            S[x]=*i;
            D[*i]=x;
            return true;
        }

    return false;
}

void cuplaj ()
{
    for (int i=1;i<=n;i++) {
        memset(use, false, sizeof(use));
        nr += pairup(i);
    }
}

/**
 * void mark(int nod_stanga) {
 *     uita-te prin vecini
 *     daca gasesti un vecin nemarcat
 *        marcheaza-l pe vecin
 *        demarcheaza D[vecin]
 *        apeleaza mark(D[vecin])
 */

 void mark(int x)
 {
     for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
         if (!dr[*i])
         {
             dr[*i]=true;
             st[D[*i]]=false;
             mark(D[*i]);
         }
 }

int main()
{
    int m,x,y;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y;
        a[x].push_back(y);
    }

    cuplaj();
    for (int i=1;i<=n;i++)
        if (S[i])
            st[i]=true;
    for (int i=1;i<=n;i++)
        if (!S[i])
            mark(i);
    out << 2 * n - nr << "\n";
    for (int i=1;i<=n;i++)
        out<<(!st[i])+2*(!dr[i])<<"\n";

    return 0;
}