#include <cstdio>
#include <vector>
#define Nmax 8500

using namespace std;

int n,i,m,x,y,SOL;
int st[Nmax*2];
vector <int> g[Nmax*2];
bool sel[Nmax*2];


bool cupleaza(int nod)
{
    if (sel[nod]) return false;
    sel[nod]=true;
    for (int i=0;i<g[nod].size();++i)
    if (!st[g[nod][i]])
     {
         st[nod]=g[nod][i], st[g[nod][i]]=nod;
         return true;
     }

    for (int i=0;i<g[nod].size();++i)
    if (cupleaza(st[g[nod][i]]))
    {
        st[nod]=g[nod][i], st[g[nod][i]]=nod;
        return true;
    }

    return false;
}

inline void cuplaj()
{
    bool ok=true;
    for (;ok;)
    {
        ok=false;
        for (i=1;i<=n;++i) sel[i]=false;
        for (int i=1;i<=n;++i)
        if (!st[2*i]) ok|=cupleaza(2*i);
    }
}

int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);

    scanf("%d %d", &n, &m); int maxi=0; int crt=0;
    for (i=1;i<=m;++i)
    {
        scanf("%d %d", &x, &y);
        g[2*x].push_back(2*y+1);
    }

    cuplaj();
    for (i=1;i<=n;++i) if (st[2*i]) SOL++;
    printf("%d\n", 2*n-SOL);
    for (i=1;i<=n;++i)
    {
        if (!st[2*i] && !st[(2*i+1)*2]) printf("3\n");
        else if (!st[2*i]) printf("1\n");
        else if (!st[(2*i+1)*2]) printf("2\n");
        else printf("0\n");
    }



    return 0;
}