CSES - Datatähti 2018 loppu - Tietoverkko
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Syrjälän tietoverkossa on nn tietokonetta, joiden välillä on nn 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 nn: tietokoneiden määrä. Koneet on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on nn riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: koneiden aa ja bb 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 (1,2)(1,2), (2,3)(2,3), (5,6)(5,6) ja (6,7)(6,7).

Osatehtävä 1 (28 pistettä)

  • 2n1002 \le n \le 100

Osatehtävä 2 (72 pistettä)

  • 2n1052 \le n \le 10^5