- Time limit: 1.00 s
- Memory limit: 512 MB
Syrjälän tietoverkossa on tietokonetta, joiden välillä on yhteyttä. Tällä hetkellä on mahdollista lähettää viesti minkä tahansa kahden koneen välillä.
Tehtäväsi on laskea, moniko yhteyksistä on välttämätön: jos yhteyden poistaa, niin jonkin kahden koneen välillä ei enää voi lähettää viestiä.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku : tietokoneiden määrä. Koneet on numeroitu .
Sitten syötteessä on riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua ja : koneiden ja välillä on yhteys.
Kahden koneen välillä on enintään yksi yhteys, ja mistään koneesta ei ole yhteyttä itseensä.
Tuloste
Tulosta yksi kokonaisluku: välttämättömien yhteyksien määrä.
Esimerkki
Syöte:
7 1 2 2 3 2 4 4 5 2 5 5 6 6 7
Tuloste:
4
Selitys: Välttämättömät yhteydet ovat , , ja .