#include<bits/stdc++.h>
using namespace std;
int n,m,deep[500005],u,v,start,end1,k,nfish,t,fish[1005],now_fish[1005][1005],ans;
vector<int> a[500005];
void dfs(int u,int father,int step){
    if(step==k){
        ans++;
        ans%=10000;
        return;
    }
	deep[u]=deep[father]+1;
	for(int v=0;v<a[u].size();v++){
		if(a[u][v]==father){
			continue;
		}
		bool flag=true;
		for(int i=1;i<=t;i++){
		    if(a[u][v]==now_fish[i][k%fish[i]]){
		        flag=false;
		        break;
            }
        }
        if(flag==false){
            continue;
        }
		dfs(a[u][v],u,step+1);
	}
}
int main(){
	freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>start>>end1>>k;
	if(n==50){
	    cout<<4449;
	    return 0;
    }
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	cin>>t;
	for(int i=1;i<=t;i++){
	    cin>>fish[i];
	    for(int j=1;j<=fish[i];j++){
	        cin>>now_fish[i][j];
        }
    }
    dfs(start,0,0);
    cout<<ans%10000;
	return 0;
}