#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#define MAXN 8500

using namespace std;

vector<int> graf[MAXN];
int n, m;
int par[MAXN], st[MAXN];
bitset<MAXN> viz;

void citire()
{
	int x, y;
	scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
        graf[x].push_back(y);
    }
}

int cupleaza(int nod)
{
	if (viz[nod]) return 0;
	viz[nod] = 1;
    for (int i = 0, t = graf[nod].size(); i < t; i++)
		if (par[graf[nod][i]] == 0 || cupleaza(par[graf[nod][i]])) {
			par[graf[nod][i]] = nod;
			st[nod] = graf[nod][i];
			return 1;
		}
	return 0;
}

void cuplaj()
{
	for (int ok = 1; ok; viz = 0) {
		ok = 0;
		for (int i = 1; i <= n; i++)
			if (st[i] == 0)
				ok |= cupleaza(i);
	}
	/// DEBUG
//	for (int i = 1; i <= n; i++)
//		printf("%d : %d\n", i, st[i]);
}

bitset<2*MAXN> sup;
void addSup(int nod)
{
    for (int i = 0, t = graf[nod].size(); i < t; i++) {
		int y = graf[nod][i]+n;
		if (!sup[y]) {
            sup[y] = 1;
            sup[par[y-n]] = 0;
            addSup(par[y-n]);
		}
    }
}
void suport_minim()
{
    for (int i = 1; i <= n; i++)
		if (st[i])
			sup[i] = 1;
    for (int i = 1; i <= n; i++)
		if (!st[i])
			addSup(i);
}
int feli[MAXN];
void afisare()
{
	int nr = 0;
	for (int i = 1; i <= n; i++)
		if (sup[i] == 0)
			feli[i] |= 1, nr++;
	for (int i = n+1; i <= 2*n; i++)
        if (sup[i] == 0)
			feli[i-n] |= 2, nr++;
	printf("%d\n", nr);
	for (int i = 1; i <= n; i++)
		printf("%d\n", feli[i]);
}

int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);

	citire();
	cuplaj();
	suport_minim();
	afisare();

    return 0;
}