#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]=1; //ramane doar primul felinar aprins
else if(f[x]==2) 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]=2; //ramane doar al doilea felinar aprins
else if(f[x]==1) 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;
}