C++ :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define Mod 10000
#define Maxn 101
using namespace std;
int N,M,st,en,step,nfish;
vector<int> fish[Maxn];
class Matrix{
	public:
	int ele[Maxn][Maxn],n,m;
	Matrix(){
		n=0;m=0;
		memset(ele,0,sizeof(ele));
	}
	Matrix operator*(const Matrix a){
		Matrix c;
		c.n=n; c.m=a.m;
		for(int i=1;i<=c.n;i++)
			for(int j=1;j<=c.m;j++)
				for(int k=1;k<=a.m;k++){
					c.ele[i][j]+=ele[i][k]*a.ele[k][j];
					c.ele[i][j]%=Mod;
				}
		return c;
	}
	void print(){
		cout<<"size: "<<n<<' '<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
				cout<<ele[i][j]<<' ';
			cout<<endl;
		}
	}
	void empty(int N){
		n=N; m=N;
		for(int i=1;i<=N;i++) ele[i][i]=1;
	}
} G[21],Gr;
Matrix Pow(Matrix a,long long n){
	Matrix res; res.empty(N);
	for(;n;n>>=1,a=a*a) if(n&1) res=res*a;
	return res;
}
void work(){
	int p=step/12;
	Matrix Ans;
	Ans.n=1; Ans.m=N; Ans.ele[1][st]=1;
	Ans=Ans*Pow(Gr,p);
	for(int i=1;i<=step-12*p;i++) Ans=Ans*G[i];
	cout<<Ans.ele[1][en]%Mod<<endl;
}
void init(){
	int x,y;
	cin>>N>>M>>st>>en>>step;
	st++; en++;
	G[0].n=N; G[0].m=N;
	for(int i=1;i<=M;i++){
		cin>>x>>y;
		G[0].ele[y+1][x+1]=1;
		G[0].ele[x+1][y+1]=1;
	}
	int T;
	cin>>nfish;
	for(int i=1;i<=nfish;i++){
		cin>>T;
		for(int j=1;j<=T;j++){
			cin>>x;
			fish[i].push_back(x+1);
		}
	}
	for(int t=1;t<=12;t++){
		G[t]=G[0];
		for(int i=1;i<=nfish;i++){
			int tmp=t%fish[i].size();
			for(int j=1;j<=N;j++){
				G[t].ele[j][fish[i][tmp]]=0;
			}
		}
	}
	Gr=G[1];
	for(int i=2;i<=12;i++) Gr=Gr*G[i];
}
int main(){
	init();
	work();
	return 0;
}