32340번 - 트리 장인

문제

세종이는 한양에서 유명한 트리 장인이다. 어떤 그래프라도 들고 오면 멋진 트리로 탈바꿈해준다!

정점이 $N$개, 간선이 $M$개인 단순 그래프가 주어진다. 단순 그래프란, 각 간선이 서로 다른 두 점을 이으며, 어떤 두 정점 $u,ドル $v$에 대해서도 $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 \lt v_i \le N;$ $(u_i, v_i) \ne (u_j, v_j) )$

출력

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

제한

힌트