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

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

Tuloste

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

Rajat

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

Esimerkki

Syöte:

5
1 2
1 3
3 4
3 5

Tuloste:

2
2 4
4 5