#include <fstream>
#include <vector>
#define VAL 9005

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

int N, M, i, j, A, B;
int L[VAL], R[VAL], ANS;
int LG[VAL], RG[VAL];
bool ok[VAL], nemodif;
vector <int> G[VAL];

bool Cuplaj(int nod)
{
    int nod2;
    vector <int> :: iterator it;
    if (ok[nod]==true)
      return false;
    ok[nod]=true;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        nod2=*it;
        if (R[nod2]==0)
        {
            L[nod]=nod2;
            R[nod2]=nod;
            LG[nod]=1;
            ANS++;
            return true;
        }
    }
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        nod2=*it;
        if (Cuplaj(R[nod2])==true)
        {
            L[nod]=nod2;
            R[nod2]=nod;
            LG[nod]=1;
            return true;
        }
    }
    return false;
}

void DFS(int nod)
{
    int nod2;
    vector <int> :: iterator it;
    for (it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        nod2=*it;
        if (RG[nod2]==0)
        {
            RG[nod2]=1;
            LG[R[nod2]]=0;
            DFS(R[nod2]);
        }
    }
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B;
        G[A].push_back(B);
    }
    while (nemodif==false)
    {
        nemodif=true;
        for (i=1; i<=N; i++)
          ok[i]=false;
        for (i=1; i<=N; i++)
          if (L[i]==0 && Cuplaj(i)==true)
            nemodif=false;
    }
    fout << 2*N-ANS << '\n';
    for (i=1; i<=N; i++)
      if (LG[i]==0)
        DFS(i);
    for (i=1; i<=N; i++)
    {
        if (LG[i]>0 && RG[i]>0)
          fout << 0;
        if (LG[i]==0 && RG[i]>0)
          fout << 1;
        if (LG[i]>0 && RG[i]==0)
          fout << 2;
        if (LG[i]==0 && RG[i]==0)
          fout << 3;
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}