CSES - Tietoverkko
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Syrjälän tietoverkko muodostuu nn koneesta, joiden välillä on n1n-1 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 nn: koneiden määrä. Koneet on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on n1n-1 riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: koneiden aa ja bb välillä on yhteys. Kaikki yhteydet ovat kaksisuuntaisia.

Tuloste

Tulosta ensin kokonaisluku kk: pienin mahdollinen lisättävien yhteyksien määrä. Tulosta sitten kk riviä, joista jokainen kuvaa yhden uuden yhteyden. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 3n1053 \le n \le 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

5
1 2
1 3
3 4
3 5

Tuloste:

2
2 4
4 5