#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 2*8192;
int n, m;

struct edge
{
    int cap, flux;
    int e, v;
    edge(){}
    edge(int a, int b, int c, int d)
    {
	e = a; v = b; cap = c; flux = d;
    }
};

struct nod
{
    int dest;
    int nr;
    nod(){}
    nod(int a, int b)
    {
	dest = a; nr = b;
    }
};

/*
vector<int> adj[maxn];

vector<edge> e[maxn];
vector<edge> rev[maxn];

int nrev[maxn];
int p[maxn];
*/

vector<edge> e;
vector<nod> g[maxn];

nod p[maxn];
int viz[maxn];

int s[maxn];
int sl[maxn], sr[maxn];

void read()
{
    scanf("%d%d", &n, &m);
    
    int i = m;
    m = -1;
    for (; i; --i)
    {
	int x, y; scanf("%d%d", &x, &y);
	y += n;

	e.push_back(edge(x, y, 1, 0)); 
	g[x].push_back(nod(y, ++m)); 
	e.push_back(edge(y, x, 0, 0));
	g[y].push_back(nod(x, ++m));
    }

    for (int i = 1; i <= n; ++i)
    {
	e.push_back(edge(0, i, 1, 0));
	g[0].push_back(nod(i, ++m)); 
	e.push_back(edge(i, 0, 0, 0));
	g[i].push_back(nod(0, ++m));
    }

    for (int i = n + 1; i <= 2 * n; ++i)
    {
	e.push_back(edge(i, 2 * n + 1, 1, 0));
	g[i].push_back(nod(2 * n + 1, ++m));
	e.push_back(edge(2 * n + 1, i, 0, 0));
	g[2 * n + 1].push_back(nod(i, ++m)); 
    }
}


int bfs()
{ 
    queue<int> Q;
    memset(viz, 0, sizeof(viz));
    Q.push(0); viz[0] = 1;

    while(!Q.empty())
    {
	int now = Q.front();
	Q.pop();

	for (int i = 0; i < g[now].size(); ++i)
	{ 
	    int next = g[now][i].dest; int en = g[now][i].nr;
	    if (viz[next]) continue;
	    if (e[en].cap - e[en].flux <= 0) continue;

	    p[next].dest = now;
	    p[next].nr = en;
	    if (next == 2 * n + 1) return 1;

	    Q.push(next);
	}
    }

    return 0;
}

int maxflow = 0;

void flux()
{

    while (bfs())
    {
	for (int i = 2 * n + 1; i != 0; i = p[i].dest) 
	{ 
	    //hmm 
	    int en = p[i].nr; 
	    e[en].flux++; 

	    en++;
	    e[en].flux--;
	}

	++maxflow;
    }

    for (int i = 1; i <= n; ++i)
	for (int j = 0; j < g[i].size(); ++j)
	{ 
	    int en = g[i][j].nr;
	    
	    if (g[i][j].dest == 2 * n + 1) continue;
	    if (e[en].flux == 1 && e[en].flux + e[en + 1].flux == 0) 
	    {
		s[i] = 1; 
		sl[g[i][j].dest] = i;
	    }
	}
}

void support(int x)
{ 
    for (int i = 0; i < g[x].size(); ++i)
    {
	int next = g[x][i].dest; int en = g[x][i].nr;
	if (s[next] || next == 0) continue;

	s[next] = 1;
	s[sl[next]] = 0;
	support(sl[next]);
    }
}

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

    read();

    flux();
    for (int i = 1; i <= n; ++i) if (!s[i]) support(i);

    printf("%d\n", 2 * n - maxflow);

    for (int i = 1; i <= n; ++i)
    {
	int out = 0;
	if (!s[i]) ++out;
	if (!s[i + n]) out += 2;
	printf("%d\n", out);
    }
    
    return 0;
}