트리 장인

세종이는 한양에서 유명한 트리 장인이다. 어떤 그래프든 가져오면 멋진 트리로 바꿔 준다!

정점이 $N$개, 간선이 $M$개인 단순 그래프가 주어진다. 단순 그래프란 각 간선이 서로 다른 두 정점을 잇고, 임의의 두 정점 $u$, $v$를 잇는 간선이 둘 이상 존재하지 않는 그래프이다.

세종이는 정점 $1, 2, \ldots, N$ 중 두 정점을 잇는 새 간선을 0개 이상 적절히 추가하여 이 그래프를 트리로 만든다.

세종이는 작업을 시작하기 전에 이렇게 트리로 만드는 방법이 몇 가지인지 가늠해 보려 한다. 세종이를 도와 그 방법의 수가 $K$를 넘는지 확인하고, 넘지 않는다면 정확한 수를 구하자. 단, 추가한 간선의 집합이 다를 때에만 서로 다른 방법으로 본다. 모든 간선은 방향이 없다.

첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($2 \le N \le 100\,000$, $1 \le M \le 200\,000$, $1 \le K \le 3\,000$)

이후 $M$개의 줄에 걸쳐 $i$번째 간선이 잇는 두 정점 $u_i$, $v_i$가 공백으로 구분되어 주어진다. ($1 \le u_i < v_i \le N$, $(u_i, v_i) \ne (u_j, v_j)$)

조건대로 그래프를 트리로 만드는 방법의 수가 $K$를 넘으면 -1을, 넘지 않으면 정확한 수를 출력한다.