Tiedossasi on Syrjälän seudun kaupungit ja niiden väliset tiet. Jokaisella tiellä on kumpaankin suuntaan bussiyhteys.

Uolevi on luvannut viedä Maijan kiertomatkalle, joka alkaa ja päättyy samassa kaupungissa. Matkalla tulee olla vähintään kolme kaupunkia, eikä samassa kaupungissa saa käydä monta kertaa.

Kiertomatkan hinta on teiden määrä kiertomatkan aikana. Tehtäväsi on määrittää halvin mahdollinen hinta.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu 1,2,\ldots,n.

Sitten syötteessä on m riviä, joista kullakin on kaksi kokonaislukua a ja b: kaupunkien a ja b välillä on tie.

Voit olettaa, että mistään kaupungista ei ole tietä itseensä ja kahden kaupungin välillä on enintään yksi tie.

Tuloste

Tulosta yksi kokonaisluku: halvin mahdollinen kiertomatkan hinta.

Jos kiertomatka ei ole edes mahdollinen, tulosta -1.

Rajat

• 1 \le n \le 1000
• 1 \le m \le 25000

Esimerkki

Syöte:

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

Tuloste:

3

Selitys: Mahdollinen kiertomatka on 2 \rightarrow 5 \rightarrow 4 \rightarrow 2.