#include <fstream>
#include <vector>
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
bool fost[20011];
vector <int> in,out,v[20011];
int n;
void solve(int k)
{
    fost[k]=1;
    if(k>n)
        out.push_back(k);
    else
        in.push_back(k);
    for(auto it=v[k].begin();it!=v[k].end();it++)
        if(fost[*it]==0)
            solve(*it);
}
bool nouse[20011];
int m,felin,x,y,i,j;
int main()
{
    f>>n>>m;
    felin=n*2;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x+n].push_back(y);
        v[y].push_back(x+n);
    }
    //x+n->out
    //x->in
    for(i=1;i<=n;i++)
    {
        if(fost[i]==0)
        {
            in.clear();
            out.clear();
            solve(i);
            felin=felin-min(in.size(),out.size());
            if(in.size()<out.size())
                for(j=0;j<in.size();j++)
                    nouse[in[j]]=1;
                else
                for(j=0;j<out.size();j++)
                    nouse[out[j]]=1;
        }
        if(fost[i+n]==0)
        {
            in.clear();
            out.clear();
            solve(i+n);
            felin=felin-min(in.size(),out.size());
            if(in.size()<out.size())
                for(j=0;j<in.size();j++)
                    nouse[in[j]]=1;
                else
                for(j=0;j<out.size();j++)
                    nouse[out[j]]=1;
        }
    }
    g<<felin<<'\n';
    for(i=1;i<=n;i++,g<<'\n')
    {
        if(nouse[i]==1 && nouse[i]==1)
        {
            g<<0;
            continue;
        }
        if(nouse[i]==1)
        {
            g<<1;
            continue;
        }
        if(nouse[i+n]==1)
        {
            g<<2;
            continue;
        }
        g<<3;
    }
    return 0;
}