星际大学生程序设计竞赛（ICPC）即将举行，是时候选择一支代表我们星球参加这一盛大赛事的队伍了。ICPC主席已经向所有想要参赛的星球宣布了今年比赛的队伍人数。地球ICPC委员会需要组建一支恰好包含该人数的队伍。

为了最大化队员之间的兼容性和团队合作，一组人可以组建一支队伍，当且仅当对于该组中的任意一对成员 $(u, v)$，$u$ 必须指定 $v$ 为他想合作的人，反之亦然。此外，作为参赛者要求的一部分，如果两个参赛者互相指定对方为想合作的人，那么他们要么都入选队伍，要么都不入选。

地球有 $n$ 名有资格参加今年比赛的候选人。地球已经收集了关于每个参赛者想和谁成为队友的数据。有了这些信息，你能帮助地球ICPC委员会确定有多少种方法来选择一支符合要求人数的队伍参加即将到来的比赛吗？如果两种队伍配置中至少有一个成员在其中一种配置中而不在另一种配置中，则认为它们是不同的。

输入格式

输入的第一行包含三个整数 $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$ 是今年ICPC要求的确切队伍人数。

参赛者编号为 $1$ 到 $n$。接下来的 $m$ 行每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$，$x \ne y$），表示参赛者 $x$ 想与参赛者 $y$ 合作。保证所有这些条目都是唯一的。

输出格式

输出一个整数，表示地球ICPC委员会为即将到来的ICPC选择队伍的方法数。

样例

输入样例 1

7 7 2
1 2
2 3
3 1
4 5
5 4
6 7
7 6

输出样例 1

2