U dalekom kraljevstvu postoji magični labirint s \(n\) soba, svaka označena brojem od 1 do \(n\). Heroj naše priče, princ Ivan, mora proći kroz labirint od sobe 1 do sobe \(n\) kako bi spasio princezu. Međutim, labirint je začaran i princ Ivan smije ići iz sobe sa manjim brojem prema sobi sa veći brojem samo ako postoji magični tunel između njih. Dobra vještica je dala princu magični amulet koji može iskoristiti najviše \(k\) puta da se pomakne iz sobe s većim brojem u sobu s manjim brojem ali opet samo ako postoji magični tunel između njih.

Tvoj zadatak je pomoći princu Ivanu da pronađe najkraći put od sobe 1 do sobe \(n\), koristeći svoju moć amuleta na najefikasniji način.

Zadatak

Napiši program koji će odrediti najkraći put od čvora 1 do čvora \(n\) u grafu s \(n\) čvorova, uzimajući u obzir da se može pomaknuti iz čvora s većim indeksom u čvor s manjim indeksom najviše \(k\) puta.

Ulazni podatci

U prvom retku nalazi se tri broja, \(n\) broj čvorova u grafu, \(m\) broj bridova i \(k\) maksimalni broj puta koji se može pomaknuti iz čvora s većim indeksom u čvor s manjim indeksom (\(n\), \(m\) ≤ 1000, \(k\) ≤ \(n\)).

Zatim slijedi \(m\) redaka, u svakom retku dva broja \((u, v)\) koji označava neusmjereni brid \(u - v\), odnosno iz čvora \(u\) smijemo ići u čvor \(v\) i obratno.

Izlazni podatci

Samo jedan broj, duljina najkraćeg puta od čvora 1 do čvora \(n\), ili -1 ako put ne postoji.

Podzadatci

Primjer

Ulaz primjera 1:

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

Izlaz primjera 1:

3

Objašnjenje:

Najkraći put od čvora 1 do čvora 5 je \(1 \to 2 \to 4 \to 5\), s duljinom 3.

Ulaz primjera 2:

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

Izlaz primjera 2:

2

Objašnjenje:

Najkraći put od čvora 1 do čvora 6 je \(1 \to 2 \to 6\), s duljinom 2.

Ulaz primjera 3:

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

Izlaz primjer 3:

4

Objašnjenje:

Nakraći put je \(1 \to 3 \to 4 \to 5 \to 6\). Kraći put bi bio \(1 \to 3 \to 2 \to 6\) ali ne smijemo napraviti \(3 \to 2\) jer nam je amulet prazan.