Kaaleppi on juuri ryöstänyt pankin ja aikoo paeta kaupungista sataman kautta. Kuitenkin poliisi haluaa pysäyttää hänet sulkemalla joitakin katuja.

Mikä on pienin määrä katuja, jotka poliisin täytyy sulkea, jotta ei ole mitään reittiä pankista satamaan?

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja m: risteysten ja katujen määrä. Risteykset on numeroitu 1,2,\dots,n. Pankki on risteyksessä 1 ja satama on risteyksessä n.

Sitten tulee m riviä, jotka kuvaavat kadut. Jokaisella rivillä on kaksi kokonaislukua a ja b: risteysten a ja b välillä on katu. Kaikki kadut ovat kaksisuuntaisia, ja kahden risteyksen välillä on enintään yksi katu.

Tuloste

Tulosta kokonaisluku k: pienin mahdollinen suljettavien katujen määrä. Tulosta tämän jälkeen k riviä, jotka kuvaavat kadut. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

• 2 \le n \le 500
• 1 \le m \le 1000
• 1 \le a,b \le n

Esimerkki

Syöte:

4 5
1 2
1 3
2 3
3 4
1 4

Tuloste:

2
3 4
1 4