Županijsko natjecanje 2018. godine za 3. i 4. razred Srednje Škole - 2. zadatak

Nakon mnogo godina bavljenja umjetnošću, mladi Florijan želi se zaposliti u jednom konglomeratu. Ondje je zaposleno N osoba označenih brojevima od 1 do N, od koji su neki stažisti. Florijan poznaje sve stažiste u tom poduzeću i fasciniran je masivnošću hijerarhije.

U hijerarhiji poduzeća vrijedi da svaki zaposlenik ima točno jednog šefa, osim glavnog šefa, tj. direktora koji nema šefa iznad sebe. U hijerarhiji ne postoji ciklus, tj. hijerarhija je oblika stabla. Također vrijedi da stažist ne može biti nadređen zaposlenicima koji nisu stažisti.

Razgovarajući sa stažistima, Florijan je skupio popriličan broj informacija o izgledu dijela hijerarhije. Naime, za svakog stažista saznao je tko mu je šef (moguće je da mu je šef također stažist). Florijan se sada zabavlja računajući udaljenost nekih dvaju stažista u hijerarhiji, koju računa kao broj šefova između tih stažista.

Preciznije, udaljenost u hijerarhiji za dva zaposlenika dobivamo tako da, penjući se po hijerarhiji počevši od njih, ubrojimo sve njihove izravne i neizravne šefove do prvog zajedničkog šefa (uključujući i njega). Ako je jedan od promatranih dvaju zaposlenika nadređen drugome (izravno ili neizravno), brojimo samo šefove koji se u hijerarhiji nalaze strogo između njih.

Pomozite mladom Florijanu odrediti najveću udaljenost dvaju stažista u cijeloj hijerarhiji, ako je taj broj moguće odrediti (ne zanimaju ga koji su točno stažisti najudaljeniji).

ULAZNI PODACI

U prvom retku nalaze se dva prirodna broja N i M, ukupan broj zaposlenika u poduzeću i broj stažista (2 ≤ M < N ≤ 100 000).

U sljedećih M redaka nalaze se po dva prirodna broja S i Š, oznaka stažista i njegovog šefa (2 ≤ S, Š ≤ N, S ≠ Š). Nijedan stažist neće imati dva šefa

IZLAZNI PODACI

U jedini redak ispišite traženi najveći broj šefova između dvaju stažista. Ako taj broj nije moguće odrediti, ispišite -1.

PRIMJERI TEST PODATAKA

ulaz

5 4
2 1
3 2
4 3
5 4

izlaz

2

ulaz

7 4
1 2
2 3
4 5
5 6

izlaz

-1

ulaz

3 2
2 1
3 1

izlaz

1

Pojašnjenje prvog primjera: Između stažista 5 i 2 postoje dva šefa: 4 i 3

Pojašnjenje drugog primjera: Zaposlenik 7 može biti šef zaposleniku 3, a i zaposleniku 6; također je moguće da je zaposlenik 6 šef zaposlenika 3. Zbog nedostatka informacija ne možemo biti sigurni u najveći broj šefova između dvaju stažista.