#include<iostream>#include<sstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>using namespace std;const double eps(1e-8);typedef long long lint;#define clr(x) memset( x , 0 , sizeof(x) )#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clrs( x , y ) memset( x , y , sizeof(x) )const int Maxn = 110;struct Big { int a[Maxn]; int l; void Clear() { memset(a, 0, sizeof(a)); l = 1; } Big operator + (const Big & q) const { Big now; now.Clear(); now.l = max(l, q.l); for (int i = 1; i <= now.l; i ++) now.a[i] = a[i] + q.a[i]; for (int i = 1; i <= now.l + 2; i ++) if (now.a[i] >= 10) { now.a[i + 1] += now.a[i] / 10; now.a[i] %= 10; } if (now.a[now.l + 1] != 0) now.l ++; return now; } Big operator * (const Big & q) const { Big now; now.Clear(); now.l = l + q.l; for (int i = 1; i <= l; i ++) for (int j = 1; j <= q.l; j ++) now.a[i + j - 1] += a[i] * q.a[j]; for (int i = 1; i <= now.l; i ++) if (now.a[i] >= 10) { now.a[i + 1] += now.a[i] / 10; now.a[i] %= 10; } if (now.a[now.l] == 0) now.l --; return now; } void Show() { while (l > 1 && a[l] == 0) l --; for (int i = l; i >= 1; i --) printf("%d", a[i]); puts(""); }} c[Maxn][Maxn], dp[Maxn][Maxn];int g[Maxn][Maxn];int flag[Maxn], bg[Maxn];int n, m, k, scnt;int ind[Maxn], outd[Maxn], num[Maxn], bj[Maxn];Big Solve() { for (int i = 0; i <= scnt; i ++) for (int j = 0; j <= k; j ++) dp[i][j].Clear(); memset(flag, 0, sizeof(flag)); for (int i = 1; i <= scnt; i ++) { if (ind[i] == 0) flag[i] = true; if (outd[i] == 0) flag[i] = true; } dp[0][0].a[1] = 1; for (int i = 1; i <= scnt; i ++) { int deep = 0; if (flag[i]) deep = 1; for (int j = k; j >= 0; j --) { for (int t = num[i]; t >= deep; t --) { if (j < t) continue; dp[i][j] = dp[i][j] + dp[i - 1][j - t] * c[num[i]][t]; } } } return dp[scnt][k];}int main(){ for (int i = 0; i <= 100; i ++) for (int j = 0; j <= 100; j ++) c[i][j].Clear(); for (int i = 0; i <= 100; i ++) for (int j = 0; j <= i; j ++) if (j == 0) c[i][j].a[1] = 1; else { c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; } while (scanf("%d%d%d", &n, &m, &k) == 3) { memset(g, 0, sizeof(g)); memset(ind, 0, sizeof(ind)); memset(outd, 0, sizeof(outd)); memset(bj, 0, sizeof(bj)); memset(num, 0, sizeof(num)); scnt = 0; int a, b; for (int i = 1; i <= m; i ++) { scanf("%d%d", &a, &b); g[a][b] = true; } for (int k = 1; k <= n; k ++) for (int j = 1; j <= n; j ++) for (int i = 1; i <= n; i ++) { if (i == j || j == k || i == k) continue; if (g[i][k] && g[k][j]) g[i][j] = true; } for (int i = 1; i <= n; i ++) { if (! bj[i]) { bj[i] = ++scnt; for (int k = i + 1; k <= n; k ++) if (g[i][k] && g[k][i]) bj[k] = scnt; } } for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (g[i][j] && bj[i] != bj[j]) { outd[bj[i]] ++, ind[bj[j]] ++; } for (int i = 1; i <= n; i ++) num[bj[i]] ++; Solve().Show(); puts(""); } return 0;}
