25452번 - Snagator 다국어

문제

Č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 $A_i$ ima veću snagu od natjecatelja s oznakom $B_i$.” (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 $A_i$ imat će veću snagu od natjecatelja s oznakom $B_i$ 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 $A_i = A_j$ i $B_i = B_j$.

입력

U prvom su retku tri prirodna broja $N,ドル $M$ i $K$ (2ドル ≤ N ≤ 300,000円,ドル 1ドル ≤ M ≤ 300,000円,ドル 2ドル ≤ K ≤ N$), iz teksta zadatka.

U $i$-tom od sljedećih $M$ redaka su po dva prirodna broja $A_i$ i $B_i$ (1ドル ≤ A_i ≤ N,ドル 1ドル ≤ B_i ≤ N,ドル $A_i ≠ B_i$), iz teksta zadatka.

출력

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$.

제한

힌트

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.

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.