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

using namespace std;

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


const int Maxn = 10003;


vector <int> G[Maxn];

int n, m, nr_e, stp;
int l[Maxn], r[Maxn], u[Maxn], s[Maxn], sl[Maxn], sr[Maxn];

void Support(int x)
{
	vector <int> :: iterator it;
	for (auto y : G[x] )
		if ( !sr[y]) {
			++stp;

			sr[y] = 1;
			sl[l[y]] = 0;
			Support(l[y]);
		}
}

int pairup(const int a)
{
    if (u[a])  return 0;
    u[a] = 1;
    for ( auto i : G[a])
        if (!l[i])
        {
			l[i] = a;
			r[a] = i;
			//sr[*it] = 1;
			sl[a] = 1;
			return 1;
		}
    for ( auto i : G[a])
        if (pairup(l[i]))
        {
			l[i] = a;
			r[n] = i;
			sl[a] = 1;
			return 1;
			}
    return 0;
}

int main()
{



    fin >> n >> nr_e;
    m = n;
    for (; nr_e --; )
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }
    for (int i = 1; i <= n; ++i)
        if (!pairup(i))
        {
			memset(u, 0, sizeof(u));
        }
    int cuplaj = 0;
    for (int i = 1; i <= n; i++)
        if ( l[i] )
            cuplaj++;
    for (int i = 1; i <= n; ++i)
		if (!sl[i])
			Support(i);
    fout << n * 2 - cuplaj << '\n';
    for (int i = 1; i <= n; ++i)
		fout << 1-sl[i]+2*(1-sr[i]) << '\n';;

    return 0;
}