#include<stdio.h>
#define infile "felinare.in"
#define outfile "felinare.out"
#define nmax (9*1000+1)
#define mmax (20*1000+1)
struct lista
	{
	int n,p; //nodul si pozitia
	} l[mmax],lt[mmax]; //lista grafului, si graful transpus
int f[nmax]; //tipul felinarelor din noduri
int p[nmax],pt[nmax]; //pozitia din lista....si pt cel transpus
int phi[nmax],phe[nmax]; // pozitia din heap-uri
int gi[nmax],ge[nmax]; //gradul interior si cel exterior
int hi[nmax],he[nmax],nrhi,nrhe; //cele doua max-heap-uri....pt gradele externe si gradele interne
int nr,mr; //numarul de noduri si de muchii

//adaugam arcul (x,y)
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
	{
	l[m].n=y; l[m].p=p[x]; p[x]=m; //adaugam in lista
	}

void citire()
	{
	int i,x,y;
	scanf("%d %d\n",&nr,&mr);
	for(i=1;i<=mr;i++)
		{
		scanf("%d %d\n",&x,&y); //avem arcul (x,y)
		add(l,p,i,x,y); //adaaugam arcul in lista normala
		add(lt,pt,i,y,x); //adaaugam arcul in lista transpusa
		ge[x]++; gi[y]++; //grestem gradul exterior al lui x
		}
	}

//adaugam un nod in heap-ul h[], avand nodurile pozitiile in ph[], si gradele g[]
void add_heap(int h[nmax], int ph[nmax], int g[nmax], int x, int nrh)
	{
	int f=nrh,t=f/2; //fiul si tatal
	while(t&&g[h[t]]<g[x]) //cat timp avem tata, si tatal este mai mic
		{
		h[f]=h[t]; ph[h[f]]=f; //coboram tatal peste copil...si ii modificam pozitia
		f=t;t=f/2; //refacem tatal si fiul
		}
	h[f]=x; ph[h[f]]=f; //adaugam nodul la pozitia corecta...si ii salvam pozitia
	}

//combina pozitia x, ai.i sa fie plasat elementul de la pozitia x corect ;))
void comb_heap(int h[nmax], int ph[nmax], int g[nmax], int x, int nrh)
	{
	int v=h[x]; //elementul ce trebuie plasat corect in heap
	int t=x,f=2*t; //tatal si fiul
	while(f<=nrh)
		{
		if(f<nrh&&g[h[f+1]]>g[h[f]]) f++; //daca are 2 copii...aleg copilul cel mai mare
		if(g[h[f]]>g[v]) //daca fiul e mai mare
			{
			h[t]=h[f]; ph[h[t]]=t; //urcam tatal..si ii modificam pozitia
			t=f; f=2*t; //refacem tatal si fiul
			}
		else f=nrh+1; //am terminat cautarea..o oprim
		}
	h[t]=v; ph[h[t]]=t; //adaugam elementul sii ii salvam pozitia
	}

//stergem primul element in heap
void sterge_heap(int h[nmax], int ph[nmax], int g[nmax], int nrh)
	{
	h[1]=h[nrh+1]; ph[h[nrh+1]]=0; ph[h[1]]=1; //punem elementul de pe ultima pozitie
	comb_heap(h,ph,g,1,nrh); //refacem heap-ul
	}

//initializam heap-urile, si felinarele
void initializare()
	{
	int i;
	for(i=1;i<=nr;i++) //trecem pe la fiecare nod
		{
		add_heap(he,phe,ge,i,++nrhe); //adaugam in heap-ul gradelor EXTERNE
		add_heap(hi,phi,gi,i,++nrhi); //adaugam in heap-ul gradelor INTERNE
		}
	for(i=1;i<=nr;i++)
		f[i]=3; //initial toate felinarele sunt aprinse
	}

void rezolvare()
	{
	int k=2*nr; //initial toate felinarele sunt aprinse
	int x,ul;
	while(ge[he[1]] || gi[hi[1]]) //cat timp avem in heap-uri
		{
		if(ge[he[1]]>=gi[hi[1]]) //daca gradul exterior este mai mare
			{
			x=he[1]; //nodul caruia trebuie sa ii stingem felinarul exterior
			ul=p[x]; //pozitia copilului
			while(ul) //cat timp x are copii
				{
				if(gi[l[ul].n]) gi[l[ul].n]--; //scadem gradul interior al copilului
				comb_heap(hi,phi,gi,phi[l[ul].n],nrhi); //refacem heap-ul dupa modificare
				ul=l[ul].p; //frasu
				}
			ge[x]=0; comb_heap(he,phe,ge,phe[x],nrhe); //punem gradul exterior la acest nod 0
			if(f[x]==3) f[x]=2; //ramane doar primul felinar aprins
			else if(f[x]==1) f[x]=0; //nu mai avem niciun felinar aprins
			}
		else //gradul interior este mai mare
			{
			x=hi[1]; //modul caruia trebuie sa ii stingem felinarul interior
			ul=pt[x]; //pozitia copilului din graful transpus
			while(ul) //cat timp are copii
				{
				if(ge[lt[ul].n]) ge[lt[ul].n]--; //cadem gradul exterior al copilului
				comb_heap(he,phe,ge,phe[lt[ul].n],nrhe);
				ul=lt[ul].p; //frasu
				}
			gi[x]=0; comb_heap(hi,phi,gi,phi[x],nrhi); //punem gradul interior 0 la acest nod
			if(f[x]==3) f[x]=1; //ramane doar al doilea felinar aprins
			else if(f[x]==2) f[x]=0; //nu mai avem niciun felinar aprins
			}
		k--; //am stins un felinar
		}
	printf("%d\n",k); //afisem numarul de felinare ramase aprinse
	}

void afisare()
	{
	int i;
	for(i=1;i<=nr;i++)
		printf("%d\n",f[i]); //afisem starea felinarelor de pe nod
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(); //citim datele din fisier
initializare(); //initializa-m heap-urile si felinarele
rezolvare(); //rezolvam si facem vectorul de felinare
afisare(); //afisem

fclose(stdin);
fclose(stdout);
return 0;
}