Nosaukums
Mežu eži (mezu_ezi)
Laika limits
0.50s
Atmiņas limits
256.0 MB
Grūtība
63%

Definīcija

Gudrinieku ciemā migrē eži no dažādiem tuvējiem mežiem. Tu viņus apturi pie Gudrinieku ciema vārtiem.

Lai neradītu nemierus, tiks ielaisti tikai tie eži, kuru meži ir nav nedraudzīgi savā starpā - pārējie tiks atraidīti un sūtīti uz blakus ciemu dzīvot.

Tev ir dots uzdevums, zinot kuru mežu eži nesadzīvo savā starpā, noteikt kurus ežus ielaist Gudrinieku ciemā un kuriem likt doties uz kaimiņu ciemu caur vilku apsēstai ielejai.

Mežu ežu savstarpēja nepatika ir abpusēja, t.i., ja mežam A nepatīk meža B iemītnieki, tad mežam B nepatīk meža A iemītnieki.


Ievaddatu raksturojums

Dots mežu skaits N (1 <= N <= 10`000) un M (1 <= M <= 200`000)

Nākamajās M rindās doti mežu pāri - A un B (A != B; 1 <= A,B <= N), kuras viens otram nepatīk. Netiek garantēts, ka šie pāri ir unikāli.


Izvaddatu raksturojums

Vienīgajā rindā jaizvada maksimālais mežu skaits, no kuriem var ielaist ežus, lai nesāktos nesaskaņas.


Piezīmes

Tiek garantēts, ka atraidīto mežu eži savā starpā nav nedraudzīgi.

Pirmajā piemērā der meži: {2, 3}

Otrajā piemērā der meži: {1, 3} vai {2, 4}


Paraugdati

Stdin
3 2
1 2
1 3
Stdout
2

Stdin
4 4
1 2
2 3
3 4
4 1
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.