Uolevin suku järjestää joka kesä sukukokouksen. Kokous pidetään muuten Syrjälässä, mutta lopuksi kaikki matkustavat Helsinkiin juhlaillalliselle, koska Syrjälässä ei ole yhtään ravintolaa.

Tiedossasi on kaikki junayhteydet, joita matkalla Syrjälästä Helsinkiin voi käyttää. Jokaisella ratavälillä menee kerran päivässä juna kumpaankin suuntaan.

Uolevin sukulaiset ovat hieman omalaatuista väkeä. Ensinnäkin jokainen haluaa matkustaa enintään yhden ratavälin päivässä. Lisäksi kukaan ei suostu matkustamaan junassa, jos kyydissä on samaan aikaan toinen sukulainen.

Mikä on pienin mahdollinen päivien määrä, jossa koko Uolevin suku pääsee Syrjälästä Helsinkiin?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$, $m$ ja $p$: asemien määrä, yhteyksien määrä sekä sukulaisten määrä. Asemat on numeroitu kokonaisluvuin $1,2,\ldots,n$. Asema 1 on Syrjälä ja asema $n$ on Helsinki.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden ratavälin. Jokaisella rivillä on kaksi kokonaislukua $a_i$ ja $b_i$: ratavälin pääteasemat.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako päivää sukulaisten matka kestää.

Rajat

• $2 \leq n \leq 50$
• $1 \leq m \leq 200$
• $1 \leq p \leq 50$
• $1 \le a_i, b_i \le n$

Esimerkki

Syöte:

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

Tuloste:

4