JHIO 2022. 4. zadatak

Čast održavanja tradicionalnog natjecanja snagatora ove godine pripala je Puli. Na natjecanju sudjeluje N snagatora iz cijele Hrvatske, a svaki ima svoju jedinstvenu snagu koju možemo predstaviti prirodnim brojem. Vito, prošlogodišnji pobjednik, ove godine sudjeluje u ulozi suca, a uz njega sudi i obožavateljica snagatorskih natjecanja Martina.

Kako bi zadivio Martinu, Vito se odlučio pohvaliti svojim sposobnostima opažanja pa joj je u svakoj od M sekundi natjecanja dao po jednu izjavu. U i-toj od tih M sekundi ponosno je rekao: “Hej, primijetio sam da natjecatelj s oznakom Ai ima veću snagu od natjecatelja s oznakom Bi .” (Vito jako brzo priča). Kada je natjecanje završilo, Vito je htio provjeriti je li Martina pratila pa ju je upitao: “Nakon koje sekunde poslije početka natjecanja, odnosno nakon koliko mojih izjava si mogla po prvi puta poredati barem K natjecatelja po njihovoj snazi?”. Napiši program koji daje odgovor na ovo pitanje.

Vitova opažanja će uvijek biti ispravna, odnosno natjecatelj s oznakom Ai imat će veću snagu od natjecatelja s oznakom Bi za svaki i. Također, Vito može u nekoj sekundi ponoviti izjavu iz neke prošle sekunde, odnosno mogu postojati različiti i i j takvi da vrijedi Ai = Aj i Bi = Bj.

Ulazni podaci

U prvom su retku tri prirodna broja N, M i K (2 ≤ N ≤ 300000, 1 ≤ M ≤ 300000, 2 ≤ K ≤ N), iz teksta zadatka.

U i-tom od sljedećih M redaka su po dva prirodna broja Ai i Bi (1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N, Ai ≠ Bi), iz teksta zadatka.

Izlazni podaci

Ispiši nakon koliko je najmanje sekundi (odnosno izjava) moguće poredati barem K natjecatelja po njihovoj snazi, a ako to nije moguće ni nakon svih M izjava ispiši -1.

Probni primjeri

Ulaz

3 4 3
2 1
2 3
2 1
3 1

Izlaz

4

Opis prvog probnog primjera: Potrebno je poredati sva tri natjecatelja po njihovoj snazi. Nakon prve izjave znamo samo da natjecatelj 2 ima veću snagu od natjecatelja 1 što nije dovoljno. Nakon druge izjave, osim informacije iz prve izjave saznajemo da natjecatelj 2 ima veću snagu od natjecatelja 3, ali to također nije dovoljno. Postoje dvije mogućnosti poretka natjecatelja koji zadovoljavaju te dvije izjave, a to su (poredak ide od najveće do najmanje snage): 2, 1, 3 i 2, 3, 1. Tek nakon četvrte izjave znamo da je pravi poredak 2, 3, 1 te tada možemo po prvi puta poredati sva tri natjecatelja po njihovoj snazi.

Ulaz

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

Izlaz

4

Opis drugog probnog primjera: Nakon prve tri izjave možemo poredati najviše dva natjecatelja, a nakon četvrte možemo poredati svih četiri pa je to izjava nakon koje možemo po prvi puta poredati barem tri natjecatelja.

Ulaz

4 2 4
1 2
2 3

Izlaz

-1