#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <queue>#include <algorithm>#include <vector>using namespace std;typedef long long ll;const int maxn=12;int n,m,p,q,k;ll dp1[maxn][1<<maxn],dp2[maxn][1<<maxn];bool g[33][33];int x,y;int sta;vector<int>cat;int count(int sta,bool op){ int res=0; int cnt=1; while (sta) { if (op && sta&1) cat.push_back(cnt); res+=(sta&1); sta>>=1; cnt++; } return res;}int main(){ while(~scanf("%d%d%d",&n,&m,&p)) { memset(g,true,sizeof g); sta=(1<<m); scanf("%d",&k); for (int i=1; i<=k; i++) { scanf("%d%d",&x,&y); g[x][y]=g[y][x]=false; } memset(dp1,0,sizeof dp1); memset(dp2,0,sizeof dp2); dp1[0][0]=1; for (int i=1; i<=n; i++) for (int j=n+1; j<=n+m; j++) if (g[i][j]) { for (int k=0; k<sta; k++) if (dp1[i-1][k]) dp1[i][k|(1<<(j-n-1))]+=dp1[i-1][k]; } ll ans=0; for (int i=0; i<sta; i++) { cat.clear(); if (count(i,1)==n) { memset(dp2,0,sizeof dp2); ll tmp=0; dp2[0][0]=1; for (int ii=1; ii<=n; ii++) for (int j=n+m+1; j<=n+m+p; j++) if (g[n+cat[ii-1]][j]) { for (int k=0; k<(1<<p); k++) if (dp2[ii-1][k]) dp2[ii][k|(1<<(j-n-m-1))]+=dp2[ii-1][k]; } for (int k=0; k<(1<<p); k++) if (count(k,0)==n) tmp+=dp2[n][k]; ans+=dp1[n][i]*tmp; } } printf("%lldn",ans); } return 0;}
