#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
#define MAX 8200
#define cout fout

typedef vector<int> :: iterator iter;
vector<int> G[MAX];

int viz[MAX], st[MAX], dr[MAX], in_s[2 * MAX], n;

bool cuplaj(int nod)
{
    if(viz[nod] == 1)
    {
        return 0;
    }
    viz[nod] = 1;
    for(iter it = G[nod].begin() ; it != G[nod].end() ; it++)
    {
        if(!st[*it])
        {
            st[*it] = nod;
            dr[nod] = *it;
            return 1;
        }
    }
    for(iter it = G[nod].begin() ; it != G[nod].end() ; it++)
    {
        if(cuplaj(st[*it]))
        {
            st[*it] = nod;
            dr[nod] = *it;
            return 1;
        }
    }
    return 0;
}

void suport(int nod)
{
    for(iter it = G[nod].begin() ; it != G[nod].end() ; it++)
    {
        in_s[*it + n] = 1;
        if(st[*it] && in_s[st[*it]])
        {
            in_s[st[*it]] = 0;
            suport(st[*it]);
        }
    }
}

int main()
{
    int m, x, y, i;
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        G[x].push_back(y);
    }
    int ok;
    do{
        ok = 0;
        for(i = 1 ; i <= n ; i++)
        {
            if(!dr[i])
                ok |= cuplaj(i);
        }

    }while(ok);
    for(i = 1 ; i <= n; i++)
    {
        if(dr[i])
        {
            in_s[i] = 1;
        }
    }
    for(i = 1 ; i <= n ; i++)
    {
        if(!in_s[i])
        {
            suport(i);
        }
    }
    int s = 0;
    for(i = 1 ; i <= n ; i++)
    {
        s += (in_s[i]^1);
        s += (in_s[i + n]^1);
    }
    cout << s << "\n";
    for(i = 1 ; i <= n ; i++)
    {
        if(in_s[i] == 1 && in_s[i + n] == 1)
        {
            cout << 0;
        }
        if(in_s[i] == 0 && in_s[i + n] == 1)
        {
            cout << 1;
        }
        if(in_s[i] == 1 && in_s[i + n] == 0)
        {
            cout << 2;
        }
        if(in_s[i] == 0 && in_s[i + n] == 0)
        {
            cout << 3;
        }
        cout << "\n";
    }
}