Se da un graf orientat simplu cu n noduri si m muchii orientate, si un nod s. Determinati lungimea celui mai scurt ciclu orientat care trece prin s (numarul de muchii ale ciclului), sau -1 daca nu exista niciunul.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii cu cate o muchie orientata. Pe ultima linie se citeste s.
- Date de iesire
- Se afiseaza lungimea celui mai scurt ciclu care trece prin s, sau -1 daca nu exista.
- Restrictii
- 1 <= n <= 300, 0 <= m <= n*(n-1)
Exemple
Exemplul 1
Intrare
3 3 1 2 2 3 3 1 1
Iesire
3
Exemplul 2
Intrare
4 4 1 2 2 3 3 4 4 1 2
Iesire
4