题目：

当然是邻接矩阵做转移矩阵来快速幂。

对于鳄鱼，好在它们周期的lcm是12，也就是每12次就又一样了。

所以把12个转移矩阵合成一下，就可以每次乘一样的，进而快速幂。%12剩下的次数暴力一下。

学到了一些方便的东西，比如struct的构造函数没有参数之类的。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=55,mod=1e4;int n,m,st,ed,k,fs;struct Matrix{    int a[N][N];    Matrix(){memset(a,0,sizeof a);}    Matrix operator*(const Matrix &b)const    {        Matrix c;        memset(c.a,0,sizeof c.a);//        for(int i=1;i<=n;i++)            for(int k=1;k<=n;k++)                for(int j=1;j<=n;j++)                    (c.a[i][j]+=a[i][k]*b.a[k][j]%mod)%=mod;        return c;    }    void init()    {        for(int i=1;i<=n;i++)a[i][i]=1;    }}r[15],ans;int main(){    scanf("%d%d%d%d%d",&n,&m,&st,&ed,&k);st++;ed++;    int x,y;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&x,&y);x++;y++;        for(int j=1;j<=12;j++)            r[j].a[x][y]=1,r[j].a[y][x]=1;    }    scanf("%d",&fs);    for(int i=1;i<=fs;i++)    {        scanf("%d",&x);        for(int j=1;j<=x;j++)        {            scanf("%d",&y);y++;            for(int k=j;k<=12;k+=x)                memset(r[k].a[y],0,sizeof r[k].a[y]);        }    }    r[13].init();    for(int i=1;i<=12;i++)r[13]=r[13]*r[i];    ans.a[1][st]=1;x=k/12;    while(x)    {        if(x&1)ans=ans*r[13];        r[13]=r[13]*r[13];x>>=1;    }    x=k%12;    for(int i=1;i<=x;i++)ans=ans*r[i];    printf("%d",ans.a[1][ed]);    return 0;}