#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
bool fost[20011];
int coup[20011];
vector <int> v[10011];
int cuplaj(int k)
{
    if(fost[k]==1)
        return 0;
    fost[k]=1;
    for(auto it=v[k].begin();it!=v[k].end();it++)
        if(coup[*it]==0)
        {
            coup[*it]=k;
            coup[k]=*it;
            return 1;
        }
    for(auto it=v[k].begin();it!=v[k].end();it++)
        if(cuplaj(coup[*it])==1)
        {
            coup[k]=*it;
            coup[*it]=k;
            return 1;
        }
    return 0;
}
bool s[20011];
void solve(int k)
{
    for(auto it=v[k].begin();it!=v[k].end();it++)
    {
        if(s[*it]==0)
        {
            s[*it]=1;
            s[coup[*it]]=0;
            solve(coup[*it]);
        }
    }
}
int n,m,i,x,y,schimb,nr;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y+n);
    }
    //x+n->out
    //x->in
    schimb=1;
    while(schimb)
    {
        schimb=0;
        memset(fost,0,sizeof(fost));
        for(i=1;i<=n;i++)
            if(coup[i]==0)
                schimb=schimb+cuplaj(i);
    }
    for(i=1;i<=n;i++)
        if(coup[i]>0)
        nr++;
    g<<n*2-nr<<'\n';
    for(i=1;i<=n;i++)
        if(coup[i]!=0)
        s[i]=1;
    for(i=1;i<=n;i++)
        if(coup[i]==0)
        solve(i);
    for(i=1;i<=n;i++,g<<'\n')
    {
        if(s[i]==1 && s[i+n]==1)
        {
            g<<0;
            continue;
        }
        if(s[i+n]==1)
        {
            g<<1;
            continue;
        }
        if(s[i]==1)
        {
            g<<2;
            continue;
        }
        g<<3;
    }
    return 0;
}