Programozás‎ > ‎Feladatok‎ > ‎

Független

Póniföld  hercegnője játszani szeretne barátaival (sok barátja van), de mivel békeszerető, nem akar olyan barátokat hívni, akik utálják egymást. (Ez veszekedést okozna, amit el akar kerülni.) 

Szerencsére Póniföldön az utóbbi időben látványosan fejlődik a közösségi média, a legnagyobb siker egy antiszociális weboldal, ahol mindenki bejelölheti, hogy kiket utál. Természetesen a hercegnő nem fér hozzá közvetlenül ezekhez adatoknak, hiszen a weboldal üzemeltetői komolyan veszik az adatvédelmi előírásokat, ezért további tárgyalásokra van szükség az adatok megszerzéséhez. 

Amíg a tárgyalások zajlanak, a hercegnő letöltheti az antiszociális gráf egy névtelen változatát. Ezt használhatja arra, hogy megbecsülje, legfeljebb hány vendéget hívhat meg, ha nem akar egymást utáló meghívottakat a buliban.  

Szerencsére Póniföld antiszociális gráfjának van egy szép tulajdonsága: nem tartalmaz kört. (Gráfelméleti értelemben.)

Feladat

Írjunk programot, ami megadja, hogy legfeljebb hány vendégre lehet számítani.

Bemenet

Az első sor az ismerősök N számát (1 <= N <= 20000) és az utálkozások M számát (1<= M < 20000) tartalmazza. A következő M sor mindegyikében két ember i és j sorszáma olvasható (0<= i, j < N), ami azt jelenti, hogy i és j utálják egymást.

Kimenet

Egyetlen szám, a vendégek lehetséges maximális száma.

Példa

Bemenet  Kimenet
4 3
0 1
0 2
0 3
3


Tesztadatok

Címkék

A feladat forrása: BME 24 órás programozói verseny, 2012 preEC
Algoritmusok: gráfbejárás

megoldás