은하계 팀

은하계 경쟁 프로그래밍 대회(ICPC)가 곧 열리고, 우리 행성을 대표할 팀을 골라야 한다. ICPC 회장은 참가를 원하는 모든 행성에 올해 대회의 팀 인원을 알렸다. 지구 ICPC 위원회는 정확히 이 인원으로 팀을 꾸려야 한다.

팀원끼리 잘 맞도록, 집합 안의 임의의 두 구성원 $(u, v)$에 대해 $u$가 $v$를 함께 일하고 싶은 사람으로 지정하고, $v$도 $u$를 지정해야만 그 집합이 팀을 이룰 수 있다. 또한 참가자의 요구에 따라, 서로를 지정한 두 참가자는 둘 다 팀에 들어가거나 둘 다 들어가지 않는다.

지구에는 올해 대회에 참가할 자격이 있는 참가자가 $n$명 있다. 위원회는 각 참가자가 함께 일하고 싶은 사람에 대한 자료를 모았다. 이 정보를 바탕으로 필요한 인원의 팀을 고르는 방법의 수를 구하라. 한 구성원이라도 한쪽 구성에만 속하면 두 팀 구성은 서로 다른 것으로 본다.

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 10^5$, $1 \le m \le \min(n \cdot (n - 1), 10^6)$, $1 \le k \le n$). 여기서 $n$은 참가 후보자 수, $m$은 누가 누구와 함께 일하고 싶은지를 적은 항목 수, $k$는 필요한 팀의 정확한 인원이다.

참가자는 1번부터 $n$번까지 번호가 매겨진다. 이어지는 $m$개의 줄에는 각각 두 정수 $x$, $y$ ($1 \le x, y \le n$, $x \ne y$)가 주어지며, 이는 참가자 $x$가 참가자 $y$와 함께 일하고 싶어 한다는 뜻이다. 모든 항목은 서로 다르다고 보장된다.

지구 ICPC 위원회가 올해 ICPC의 팀을 고를 수 있는 방법의 수를 정수 하나로 출력한다.