#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxv 55#define mod 10000using namespace std;long long n,m,s,t,k,r,map[maxv][maxv];long long type,x,y,z,w;bool vis[maxv][13];struct matrix{    long long a[maxv][maxv];}tr[13],a,b;matrix mul(matrix a,matrix b){    matrix c;    for (long long i=1;i<=n;i++)        for (long long j=1;j<=n;j++)            c.a[i][j]=0;    for (long long i=1;i<=n;i++)        for (long long j=1;j<=n;j++)        {            for (long long k=1;k<=n;k++)                c.a[i][j]=(c.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod;        }    return c;}void get_table(){    for (long long i=1;i<=n;i++)    {        if (i==s) a.a[1][s]=1;        else a.a[1][i]=0;    }    for (long long i=1;i<=12;i++)    {        for (long long j=1;j<=n;j++)            for (long long k=1;k<=n;k++)                tr[i].a[j][k]=map[j][k];        for (long long j=1;j<=n;j++)        {            if (vis[j][i])            {                for (long long k=1;k<=n;k++)                        tr[i].a[k][j]=0;            }        }    }    for (int i=1;i<=n;i++) b.a[i][i]=1;    for (long long i=1;i<=12;i++)        b=mul(b,tr[i]);}void f_pow(matrix &a,long long y){    if (!y) return;    matrix ans=a,base=b;    while (y)    {        if (y&1) ans=mul(ans,base);        base=mul(base,base);        y>>=1;    }    a=ans;}long long get_ans(){    f_pow(a,k/12);    for (long long i=1;i<=k%12;i++)        a=mul(a,tr[i]);    printf("%d\n",a.a[1][t]);}int main(){    scanf("%lld%lld%lld%lld%lld",&n,&m,&s,&t,&k);s++;t++;    for (long long i=1;i<=m;i++)    {        scanf("%lld%lld",&x,&y);        x++;y++;        map[x][y]=map[y][x]=1;    }    scanf("%lld",&r);    for (long long i=1;i<=r;i++)    {        scanf("%lld",&type);        if (type==2)        {            scanf("%lld%lld",&x,&y);x++;y++;            for (long long j=1;j<=12;j++)            {                if (j&1) vis[y][j]=true;                else vis[x][j]=true;            }        }        else if (type==3)        {            scanf("%lld%lld%lld",&x,&y,&z);x++;y++;z++;            for (long long j=1;j<=12;j++)            {                if (j%3==1) vis[y][j]=true;                else if (j%3==2) vis[z][j]=true;                else vis[x][j]=true;            }        }        else        {            scanf("%lld%lld%lld%lld",&x,&y,&z,&w);x++;y++;z++;w++;            for (long long j=1;j<=12;j++)            {                if (j%4==1) vis[y][j]=true;                else if (j%4==2) vis[z][j]=true;                else if (j%4==3) vis[w][j]=true;                else vis[x][j]=true;            }        }    }    get_table();    get_ans();    return 0;}