#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 8200;
ifstream f("felinare.in");
ofstream g("felinare.out");
vector <int> graph [2 * N];
int n;
bool used [N];
int st [2 * N], dr [2 * N], mvc [2 * N], sol [N];

int cuplaj (int x) {
    vector <int> :: iterator it;

    if (used [x] == 1)
        return 0;
    used [x] = 1;
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (dr [*it] == 0) {
            st [x] = *it;
            dr [*it] = x;
            return 1;
        }
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (dr [*it]) {
            if (cuplaj (dr [*it]) == 1) {
                st [x] = *it;
                dr [*it] = x;
                return 1;
            }
        }
    return 0;
}

void dfs (int x) {
    vector <int> :: iterator it;

    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
       if (mvc [*it] == 0) {
           mvc [*it] = 1;
           mvc [dr [*it]] = 0;
           dfs (dr [*it]);
       }
}

int main () {
    int i, m, x, y, muchia, lim, ans = 0;
    bool flag;


    f>>n>>m;
    lim = 2 * n;
    for (i = 1; i <= m; i ++) {
        f>>x>>y;
        graph [x].push_back (y + n);
    }
    flag = true;
    while (flag) {
        flag = 0;
        memset (used, 0, sizeof (used));
        for (i = 1; i <= n; i ++)
            if (st [i] == 0) {
                if (cuplaj (i)) {
                    flag = 1;
                    ans ++;
                }
            }
    }
    for (i = 1; i <= n; i ++)
        if (st [i])
            mvc [i] = 1;
    for (i = 1; i <= n; i ++)
        if (st [i] == 0)
            dfs (i);

    ans = 2 * n - ans;
    g<<ans<<'\n';

    for (i = 1; i <= n; i ++)
      if(mvc[i]==0&&mvc[n+i]==0)
         g<<3<<'\n';
       else
         if(mvc[i]!=0&&mvc[i+n]==0)
              g<<2<<'\n';
                      else
           if(mvc[i]==0&&mvc[i+n]!=0)
                g<<1<<'\n';
            else
               g<<"0\n";


    return 0;
}