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