<마법의 사과> 탈무드 이야기

최근 루루는 테라에게 나무를 성장시키는 마법을 배웠다. 루루는 성장 마법을 능숙하게 다루기 위해 과수원의 나무들을 대상으로 연습하기로 했다.

과수원에는 $N$그루의 나무가 있으며, 나무들은 $1$번부터 $N$번까지 번호가 붙어 있다. 일부 나무 쌍은 양방향 마법 통로로 연결되어 있다.

$i$번 나무의 성장도는 $A_i$이다. 성장도는 $K$를 초과할 수 없으며, 성장도가 $K$인 나무를 완전히 성장한 나무라고 한다.

루루는 마법 통로로 직접 연결된 두 나무 $u$, $v$를 골라 성장 마법을 시전할 수 있다. 성장 마법을 시전하면 두 나무 중 하나를 선택하여, 선택한 나무의 성장도를 다음 값으로 바꾼다.

$\min(K,A_u+A_v)$

선택하지 않은 나무의 성장도는 변하지 않는다. 위 식에서 사용되는 $A_u$와 $A_v$는 마법을 시전하기 직전의 성장도이다.

루루는 모든 나무를 완전히 성장시키면 연습을 마치려고 한다.

모든 나무의 성장도를 $K$로 만드는 데 필요한 성장 마법의 최소 시전 횟수를 구하여라. 불가능하다면 $-1$을 출력하여라.

첫째 줄에 나무의 수 $N$, 마법 통로의 수 $M$, 최대 성장도 $K$가 공백으로 구분되어 주어진다. ($1\le N\le200\,000$; $$; )

모든 나무를 완전히 성장시키는 데 필요한 성장 마법의 최소 시전 횟수를 출력한다.

모든 나무를 완전히 성장시키는 것이 불가능하다면 -1을 출력한다.