- Time limit: 1.00 s
- Memory limit: 128 MB
Syrjälän tietoverkko muodostuu koneesta, joiden välillä on yhteyttä. Jokaisen kahden koneen välillä pystyy lähettämään viestin, mahdollisesti muiden koneiden kautta.
Verkon heikkoutena on, että jos siitä katkeaa yksikin yhteys, joidenkin koneiden välillä ei voi viestiä. Tehtäväsi on lisätä verkkoon pienin määrä uusia yhteyksiä, joiden ansiosta verkossa voi viestiä minkä tahansa koneiden välillä, vaikka siitä katkeaisi mikä tahansa yksi yhteys.
Syöte
Syötteessä on ensin kokonaisluku : koneiden määrä. Koneet on numeroitu kokonaisluvuin .
Sitten syötteessä on riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua ja : koneiden ja välillä on yhteys. Kaikki yhteydet ovat kaksisuuntaisia.
Tuloste
Tulosta ensin kokonaisluku : pienin mahdollinen lisättävien yhteyksien määrä. Tulosta sitten riviä, joista jokainen kuvaa yhden uuden yhteyden. Voit tulostaa minkä tahansa kelvollisen ratkaisun.
Rajat
Esimerkki
Syöte:
5 1 2 1 3 3 4 3 5
Tuloste:
2 2 4 4 5