Sinulle annetaan yhtenäinen suuntaamaton verkko, jossa on n solmua ja m kaarta. Tuota puu, jossa on vähintään n ja enintään n+m solmua, missä jokaisella kolmikolla indeksejä 1 \leq a, b, c \leq n pätee:

Puussa polulla solmusta a solmuun b on solmu c jos ja vain jos solmu c on kaikilla poluilla solmusta a solmuun b alkuperäisessä verkossa.

Voidaan osoittaa, että on aina olemassa tämän säännön täyttävä puu.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua n ja m: solmujen ja kaarten määrä verkossa.

Seuraavilla m rivillä on jokaisella pari lukuja a ja b, joka tarkoittaa että solmujen a ja b välillä on suuntaamaton kaari.

Voit olettaa verkon olevan yhtenäinen.

Tuloste

Tulosta ensimmäisellä rivillä yksi luku k: puusi koko

Tämän jälkeen tulosta k-1 riviä, jokaisella yksi kaari.

Rajat

• 1 \leq n \leq 10^{5}
• 0 \leq m \leq 2 \cdot 10^{5}

Esimerkki

Syöte:

6 7
1 2
1 3
1 4
1 5
2 3
4 5
5 6

Tuloste:

9
1 7
1 8
2 7
3 7
8 9
9 4
5 6
5 8