#include <bits/stdc++.h>
using namespace std;

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

class Graph {
  private:
    int m, n;
    vector<vector<int>> ad;
    vector<int> matchR, matchL;

    bool match(int node, vector<bool>& vis) {
        if (vis[node])
            return false;
        vis[node] = true;
        for (int nghb : ad[node])
            if (!matchL[nghb] || match(matchL[nghb], vis)) {
                matchR[node] = nghb;
                matchL[nghb] = node;
                return true;
            }
        return false;
    }

  public:
    Graph(int m, int n) :
        m(m), n(n), ad(m + 1) { }

    void addEdge(int x, int y) {
        ad[x].push_back(y);
    }

    pair<int, vector<int>> maxIndSet() {
        matchR.resize(m + 1);
        matchL.resize(n + 1);

        bool toDo;
        do {
            toDo = false;
            vector<bool> vis(m + 1);
            for (int i = 1; i <= m; i++)
                if (!matchR[i])
                    toDo |= match(i, vis);
        } while (toDo);

        pair<int, vector<int>> ans;
        for (int i = 1; i <= m; i++)
            ans.first += (bool) matchR[i];
        ans.first = m + n - ans.first;

        ans.second.resize(m);
        for (int i = 0; i < m; i++) {
            if (matchR[i])
                ans.second[i] |= 1;
            ans.second[i] |= 2;
        }
        return ans;
    }
};

int main() {
    int n, m; fin >> n >> m;
    Graph graph(n, n);
    for (int i = 0; i < m; i++) {
        int x, y; fin >> x >> y;
        graph.addEdge(x, y);
    }

    auto ans = graph.maxIndSet();
    fout << ans.first << '\n';
    for (int conf : ans.second)
        fout << conf << '\n';

    fout.close();
    return 0;
}