国王的国家有 n × K 个城市，整个国家是由 (n × K) × (n × K - 1) 条有向道路连接的，每对城市之间都有两条道路且这两条道路方向相反，国王为了方便管理国家将国家分成了 K 个部分，第 i 个部分的城市标号为 (i - 1) × n + 1, (i - 1) × n + 2, ..., i × n (1 ≤ i ≤ K)，国王自己位于 1 号城市。 其中每个部分的规划是一样的，现在国王准备修缮王国的道路系统，对于每个部分他准备关闭不经常使用的 m 条道路，因为每个部分规划是相同的，所以关闭的道路也是类似的，对于第一部分如果 u 号城市到 v 号城市的道路关闭了(1 ≤ u, v ≤ n, u ≠ v),那么其他部分的 w × n + u 号城市到 w × n + v 号城市的道路也会关闭 (1 ≤ w ≤ K - 1)。 然后国王准备在未关闭的道路里升级 n × K - 1 条道路，升级后的道路都是快速道路，并且国王可以只通过快速道路到达所有其它城市。 现在国王给你修缮道路的方案，你要给出升级道路的方案数。
Input
第一行给定三个整数 n, m, K(2 ≤ n ≤ 300, 0 ≤ m ≤ n × (n - 1), 1 ≤ K ≤ 108)。 接下来 m 行，每行两个整数 i, j(1 ≤ i ≤ n, 1 ≤ j ≤ n, i ≠ j) ,表示关闭第一部分 i 到 j 的有向道路。 数据保证没有重边。