Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Saituri

Saituri


View task | Model solution | Statistics


Saituri

Time limit:1.00 s
Memory limit:128 MB

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.

Tuloste

Tulosta yksi kokonaisluku: halvin mahdollinen kiertomatkan hinta.

Jos kiertomatka ei ole edes mahdollinen, tulosta $-1$.

Rajat
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$.