#include <fstream>
#include <vector>
#include <bitset>

#define In "felinare.in"
#define Out "felinare.out"
#define Nmax 10000

using namespace std;

vector< int >Graph[Nmax];
bitset< Nmax > viz, L, R;
typedef vector< int >::iterator IT;
int Left[Nmax], Right[Nmax], n ,sol;

inline void Read()
{
    ifstream f(In);
    int m,x,y;
    f>>n>>m;
    for(; m ; --m)
    {
        f>>x>>y;
        Graph[x].push_back(y);
    }
    f.close();
}

inline bool PairUp(const int node)
{
    if(viz[node])
        return 0;
    viz[node] = 1;
    for(IT it = Graph[node].begin();it != Graph[node].end(); ++it)
        if(!Right[*it] || PairUp(Right[*it]))
        {
            Left[node]  = *it;
            Right[*it] = node;
            return 1;
        }
    return 0;
}

inline void Coupling()
{
    int i;
    bool ok;
    do
    {
        for(i = 1,ok = 0, viz = 0;i <= n; ++i)
            if(!Left[i] && PairUp(i))
                ok = 1;
    }
    while(ok);

}

inline void Dfs(const int node)
{
    for(IT it = Graph[node].begin();it != Graph[node].end(); ++it)
        if(L[Right[*it]])
        {
            R[*it] = 1;
            L[Right[*it]] = 0;
            Dfs(Right[*it]);
        }
}

inline void MinimumVertexCover()
{
    int i, node = 0;
    for(i = 1;i <= n; ++i)
        if(Left[i])
            L[i] = 1;
        else
            node = i;
    if(node)
        Dfs(node);
}

inline void MaximumIndendentSet()
{
    ///MIS si MVC sunt complementare
    for(int i = 1;i <= n; ++i)
    {
        L[i] = L[i]^1,
        R[i] = R[i]^1;
        if(L[i])
            ++sol;
        if(R[i])
            ++sol;
    }
}

inline void Write()
{
    int i;
    ofstream g(Out);
    g<<sol<<"\n";
    for(i = 1;i <= n; ++i)
        if(!L[i] && !R[i])
            g<<"0\n";
        else
            if(L[i] && R[i])
                g<<"3\n";
        else
            if(L[i])
                g<<"1\n";
        else
            g<<"2\n";
    g.close();
}

int main()
{
    Read();
    Coupling();
    MinimumVertexCover();
    MaximumIndendentSet();
    Write();
    return 0;
}