#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;
    vector<bool> mvcL, mvcR;

    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;
    }

    void dfs(int node) {
        for (int nghb : ad[node])
            if (!mvcR[nghb]) {
                mvcR[nghb] = true;
                mvcL[matchL[nghb]] = false;
                dfs(matchL[nghb]);
            }
    }

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

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

    void mbm() {
        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);
    }

    void mvc() {
        mvcL.resize(m + 1);
        mvcR.resize(n + 1);
        for (int i = 1; i <= m; i++)
            if (matchR[i])
                mvcL[i] = true;
        for (int i = 1; i <= m; i++)
            if (!matchR[i])
                dfs(i);
    }

    pair<int, vector<int>> mis() {
        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 = 1; i <= m; i++) {
            if (!mvcL[i]) ans.second[i - 1] |= 1;
            if (!mvcR[i]) ans.second[i - 1] |= 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);
    }

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

    fout.close();
    return 0;
}