Obeleži sve kategorije koje odgovaraju problemu

У популарној игри “Змије и лестве” играч се креће од почетног поља бацајући коцкицу и померајући се онолико поља унапред колико покаже коцкица. Постоје две врсте посебних поља. Ако играч стане на неко поље на ком се налазе “лестве”, он се пење уз те лестве и прелази на оно поље са већим бројем до кога те лестве воде. Ако играч стане на неко поље на ком се налази змија, он се спушта и прелази на оно поље са мањим бројем до кога та змија води. Написати програм који одређује минималан број корака (бацања коцкице) којима играч може да стигне од почетног до завршног поља.

Напомена: Ако играч стигне на неко поље које је део циклуса састављеног од лестви и змија, он моментално губи игру и не може да стигне до циља (таква поља се морају избегавати).

Улаз

Са стандардног улаза се учитава укупан број поља \(n\) (\(5 \leq n \leq 200\)). Поља су обележена бројевима од 0 до \(n-1\). У наредном реду се налази највећи број \(k\) који се може добити бацањем коцкице (коцкицом се добијају бројеви од \(1\) до $k). Након тога се учитава укупан број \(m\) змија и лестви (\(0 \leq m \leq n\)), а затим и подаци о њима (број полазног и број долазног поља).

Излаз

На стандардни излаз исписати тражени минимални број корака. Ако није могуће стићи до циља, исписати -1.

Пример 1

Улаз

18
2
5
2 12
3 13
8 17
11 1
14 7

Излаз

3

Објашњење

Добијањем броја 2, играч са поља 0 прелази на поље 2 и затим се лествама пење до поља 12. Добијањем броја 2, долази на поље 14, одакле се змијом спушта до поља 7. Добијањем броја 1, долази на поље 8, одакле се лествама пење до циљног поља 17.

Пример 2

Улаз

5
2
2
1 3
3 1

Излаз

2

Објашњење

Играч не сме да стане на поље 1 или 3, јер ће тада изгубити због циклуса на ком се налази. Зато му је најбоље да прво дође до поља 2, па затим до поља 4.