#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

class bipart
{
public:
    vector<int> to, from;
    vector<vector<int> > edges;
    bipart(int n, int m)
    {
        this->n = n;
        this->m = m;
        edges.resize(n + 1);
        to.resize(n + 1);
        from.resize(n + 1);
    }
    void AddEdge(int x, int y)
    {
        edges[x].push_back(y);
    }
    void GetCuplaj(vector<pair<int, int> > &ret)
    {
        vector<bool> viz(n+1);
        fill(to.begin(), to.end(), 0);
        fill(from.begin(), from.end(), 0);
        bool cuplat = true;
        while(cuplat)
        {
            cuplat = false;
            fill(viz.begin(), viz.end(), false);
            for(int i = 1; i <= n; ++i)
                if(to[i] == 0 && cupleaza(i, viz, to, from))
                    cuplat = true;
        }
        for(int i = 1; i <= n; ++i)
            if(to[i] != 0)
                ret.push_back({i, to[i]});
    }
private:
    bool cupleaza(int nod, vector<bool> &viz, vector<int> &to, vector<int> &from)
    {
        if(viz[nod])
            return false;
        viz[nod] = true;
        for(auto v:edges[nod])
            if(from[v] == 0)
            {
               to[nod] = v;
               from[v] = nod;
               return true;
            }
        for(auto v:edges[nod])
            if(cupleaza(from[v], viz, to, from))
            {
                to[nod] = v;
                from[v] = nod;
                return true;
            }
        return false;
    }
    int n, m;
};

void FindSupport(const pair<int, int> &edge, vector<bool> &stSupport, vector<bool> &drSupport, bipart &gr)
{
    if(stSupport[edge.first] || drSupport[edge.second])
        return;
    drSupport[edge.second] = true;
    int from = gr.from[edge.second];
    stSupport[from] = false;
    for(auto &e:gr.edges[from])
        FindSupport(make_pair(from, e), stSupport, drSupport, gr);
}

int main()
{
    ifstream in("felinare.in");
    int n, m;
    in >> n >> m;
    bipart gr(n, n);
    vector<pair<int, int> > edges;

    int x, y;
    while(m--)
    {
        in >> x >> y;
        gr.AddEdge(x, y);
        edges.push_back({x, y});
    }
    in.close();

    vector<pair<int, int> > cuplaj;
    gr.GetCuplaj(cuplaj);
    vector<bool> stSupport(n+1), drSupport(n+1);
    for(auto &e:cuplaj)
        stSupport[e.first] = true;
    for(auto &e:edges)
        FindSupport(e, stSupport, drSupport, gr);

    ofstream out("felinare.out");
    out << 2 * n - cuplaj.size() << "\n";
    for(int i = 1; i <= n; ++i)
        out << (!stSupport[i]) + 2 * (!drSupport[i]) << "\n";
    out.close();
    return 0;
}