注意到周期234的lcm只有12，也就是以12为周期，可以走的状态是一样的

所以先预处理出这12个状态的转移矩阵，乘起来，然后矩阵快速幂优化转移k/12次，然后剩下的次数暴力转移即可

#include
    
     #include
     
      #include
      
       using namespace std;const int mod=10000;int n,m,s,t,k,x,y,nf,T,w[60];struct jz{    int a[60][60];    jz operator * (jz y)    {        jz c;        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)            {                c.a[i][j]=0;                for(int k=1;k<=n;k++)                    c.a[i][j]=(c.a[i][j]+a[i][k]*y.a[k][j])%mod;            }        return c;    }}a,b[15],ans;int main(){    scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);    s++;t++;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&x,&y);        x++;y++;        for(int j=1;j<=12;j++)            b[j].a[x][y]=b[j].a[y][x]=1;    }    scanf("%d",&nf);    for(int i=1;i<=nf;i++)    {        scanf("%d",&T);        for(int j=1;j<=T;j++)            scanf("%d",&w[j]),w[j]++;        for(int j=1;j<=12;j++)            for(int k=1;k<=n;k++)                b[j].a[k][w[j%T+1]]=0;    }    for(int i=1;i<=n;i++)        a.a[i][i]=1,ans.a[i][i]=1;    for(int i=1;i<=12;i++)        a=a*b[i];    int kk=k/12;    while(kk)    {        if(kk&1)            ans=ans*a;        a=a*a;        kk>>=1;    }    for(int i=1;i<=k%12;i++)        ans=ans*b[i];    printf("%d",ans.a[s][t]);    return 0;}