//#include <iostream>
#include <fstream>
using namespace std;

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

#define LE 20666
#define pb push_back
#include <vector>
#define x first
#define y second
#define mp make_pair
#define cout g

bool viz[LE];
vector<int> H[LE],H2[LE];
int r[LE],l[LE];
pair<int,int> E[LE];
bool MVC[LE];

bool pair_up(int nod)
{
    viz[nod]=true;
    int N=H[nod].size(),i;

    for(i=0; i<N; ++i)
    {
        int D=H[nod][i];

        if (r[D]==0)
        {
            l[nod]=D;
            r[D]=nod;
            return true;
        }

        if (viz[r[D]]==false&&pair_up(r[D]))
        {
            l[nod]=D;
            r[D]=nod;
            return true;
        }
    }

    return false;
}

void dfs(int nod)
{
    viz[nod]=true;
    int N=H2[nod].size(),i;

    for(i=0; i<N; ++i)
        if (viz[H2[nod][i]]==false)
            dfs(H2[nod][i]);
}


int main()
{
    int n,m,i;

    f>>n>>m;

    for(i=1; i<=m; ++i)
    {
        f>>E[i].x>>E[i].y;
        H[E[i].x].pb(E[i].y);
    }

    while (true)
    {
        bool okz=false;
        for(i=1; i<=n; ++i) viz[i]=false;

        for(i=1; i<=n; ++i)
            if (l[i]==0)
                okz|=pair_up(i);

        if (okz==false) break;
    }

    for(i=1; i<=m; ++i)
    {
        if (l[E[i].x]==E[i].y)
            H2[E[i].y+n].pb(E[i].x);
        else
            H2[E[i].x].pb(E[i].y+n);
    }

    for(i=1; i<=n; ++i) viz[i]=false;

    for(i=1; i<=n; ++i)
        if (viz[i]==false)
            if (l[i]==0)
                dfs(i);

    int result=0;

    for(i=1; i<=n; ++i)
        if (l[i])
        {
            if (viz[i]==false)
                MVC[i]=true;

          ++result;
        }

    cout<<n+n-result<<'\n';

    for(i=n+1; i<=n+n; ++i)
        if (r[i-n])
            if (viz[i]==true)
                MVC[i]=true;

    for(i=1; i<=n; ++i,cout<<'\n')
    {
        if (MVC[i])
        {
            if (MVC[i+n]) cout<<0;
            else cout<<2;
        }
        else
        {
            if (MVC[i+n]==false)
                cout<<3;
            else
                cout<<1;
        }
    }

    return 0;
}