只有10分

#include<bits/stdc++.h>
using namespace std;
int n,m,s,e,k,fish;
struct node{
	int a[60][60];
}t[20];
node mul(node a,node b){
	node ans;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)ans.a[i][j]=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%10000; 
			}
		}
	}
	return ans;
}
node qpow(node a,int b){
	if(b==1)return a;
	if(b%2)return mul(qpow(a,b-1),a);
	return qpow(mul(a,a),b/2);
}
void clear(int x,int y,int z){
	for(int i=0;i<12/x;i++){
		int time=i*x+y;
		for(int j=0;j<n;j++)t[time].a[z][j]=t[time].a[j][z]=0;
	}
}
int main(){
	cin>>n>>m>>s>>e>>k;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		x,y;
		for(int j=1;j<=12;j++)t[j].a[x][y]=t[j].a[y][x]=1;
	}
	cin>>fish;
	for(int i=1;i<=fish;i++){
		int r,x;
		cin>>r;
		for(int j=1;j<=r;j++){
			cin>>x;
			clear(r,j,x);
		}
	}
	node sum;
	for(int i=1;i<=12;i++){
		if(k/12!=0){
			if(i!=1)sum=mul(sum,qpow(t[i],k/12));
			else sum=qpow(t[i],k/12);
		}
		if(k-(k/12)*12>=i){
			if(k/12!=0||i!=1)sum=mul(sum,t[i]);
			else sum=t[i];
		}
	}
	cout<<sum.a[s][e]<<endl;
    return 0;
}