시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB522100.000%

문제

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

예제 입력 1

3 4 3
2 1
2 3
2 1
3 1

예제 출력 1

4

예제 입력 2

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

예제 출력 2

4

예제 입력 3

4 2 4
1 2
2 3

예제 출력 3

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