A World Wide Airlines (WWA) repülőgépeket üzemeltet. Minden gép a központi reptérről indul, először az A, majd a B repteret érinti és visszatér a központi reptérre. A járathálózatot úgy kell megtervezni, hogy a WWA minden repülőtere elérhető legyen a központi reptérről induló járatok valamelyikével. A járathálózat jellemzője, hogy nincs két olyan járat, amelynek első megállója ugyanaz lenne.
Feladat:
A WWA igazgatója csökkenteni akarja a járatszámot, megtartva az összes reptér elérhetőségét. Meg akarja tudni, mennyi az a minimális járatszám, amellyel a feladat megoldható. Írj programot, amely meghatározza ezt a számot.
Bemenet:
A bemenet első sora egy N (3<=N<=500) egész számot tartalmaz, amely megadja a repterek számát. (A reptereket az 1..N számokkal azonosítjuk.) A központi repteret az 1-es szám jelöli. A következő sor által megadott M szám (1<=M<N) a járatok számát adja meg. Az ezt követő M sorban két különböző egész szám, X és Y van egyetlen szóközzel elválasztva. A számok egy járatot adnak meg, amely útja során először az X, majd az Y repteret érinti. Minden repteret érint legalább egy járat.
Kimenet:
A programnak egyetlen egész számot kell írnia a kimenet első sorába, a minimális járatszámot, amely szükséges a repterek összekötéséhez.
Példa:
|
airlines.in |
airlines.out |
|
10
|
5 |
(ACM SZTE csapatverseny 1998)