我们模拟赛做的，我交到 luogu 上是 A 了的。

然而我们老师评测的数据把我卡成了 80pts ……

求调！

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> inline void read(T& x);
template<typename... Args> inline void read(Args& ...args);
const int MOD=10000;
template<int n,int m,typename Type=int> class Matrix{
private:
	Type v[n][m];
public:
	Matrix(){memset(v,0,sizeof 0);for(int i=0;i<min(n,m);i++) v[i][i]=1;}
	Matrix(Type val[n][m]){memcpy(v,val,sizeof v);}
	Matrix(Type val){for(int i=0;i<n;i++) for(int j=0;j<m;j++) v[i][j]=val;}
	Type* operator[](int x){return v[x];}
};
template<int n,int m,int q,typename Type> inline Matrix<n,q,Type> operator*(Matrix<n,m,Type>& x,Matrix<m,q,Type>& y);
template<int n,typename Type,typename Pow> inline Matrix<n,n,Type> qpow(Matrix<n,n,Type> a,Pow x){
	Matrix<n,n,Type> ret;
	for(;x;x>>=1,a=a*a) if(x&1) ret=ret*a;
	return ret;
}
int n,m,st,ed,fishes;
ll k;
Matrix<55,55,int> M=Matrix<55,55,int>(0);
Matrix<55,55,int> F[15];
int fish[25][5],circle[25];
signed main(){
//	freopen("t4.in","r",stdin);
//	freopen("t4.out","w",stdout);
	read(n,m,st,ed,k);
	for(int i=1,u,v;i<=m;i++){
		read(u,v);
		M[u][v]=M[v][u]=1;
	}
	read(fishes);
	for(int i=1;i<=fishes;i++){
		read(circle[i]);
		for(int j=1;j<=circle[i];j++) read(fish[i][j]);
	}
	Matrix<55,55,int> X;
	for(int l=1;l<=12;l++){
		F[l]=M;
		for(int i=1;i<=fishes;i++){
			int u=fish[i][(l+1)%circle[i]?(l+1)%circle[i]:circle[i]];
			for(int v=0;v<n;v++) F[l][v][u]=0;
		}
		X=X*F[l];
	}
	Matrix<55,55,int> ans=qpow(X,k/12);
	for(int i=1;i<=k%12;i++) ans=ans*F[i];
	printf("%d",ans[st][ed]);
	return 0;
}

template<typename T> inline void read(T& x){
	x=0;bool flag=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
	if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)-(ch&15);
	else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
}
template<typename... Args> inline void read(Args& ...args){
	int arg[]{(read(args),0)...};
	if(0) *arg=*arg;
}
template<int n,int m,int q,typename Type> inline Matrix<n,q,Type> operator*(Matrix<n,m,Type>& x,Matrix<m,q,Type>& y){
	Matrix<n,m,Type> ret(0);
	for(int i=0;i<n;i++) for(int j=0;j<q;j++) for(int k=0;k<m;k++) ret[i][j]=(ret[i][j]+x[i][k]*y[k][j])%MOD;
	return ret;
}