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