#include <bits/stdc++.h>
using namespace std;
const int N=110,M=55;
int n,m,x,y,q,u,v,d;
long long f[N][N],g[N][N],k[N][N],mod;
int main() {
    freopen("messenger.in","r",stdin);
    freopen("messenger.out","w",stdout);
    cin>>n>>m>>mod;
    while (m--) scanf("%d%d",&x,&y),k[x][y]=1;
    cin>>q;
    while (q--)
    {
        scanf("%d%d%d",&u,&v,&d);
        if (d==1)
        {
            printf("%d\n",k[u][v]);
        }
        else if (d==2)
        {
            long long ret=0;
            for (int i=1;i<=n;i++)
            {
                if (i!=u && i!=v) ret=(ret+(k[u][i] && k[i][v]))%mod;
            }
            printf("%lld\n",ret);
        }
        else
        {
            memset(g,0,sizeof(g));
            memset(f,0,sizeof(f));
            d-=3;
            for (int i=1;i<=n;i++)
            {
                if (i!=u && i!=v && k[u][i])
                {
                    for (int j=1;j<=n;j++)
                    {
                        if (j!=u && j!=v)
                        {
                            f[i][j]=k[i][j];
                        }
                    }
                }
            }
            while (d)
            {
                memset(g,0,sizeof(g));
                for (int r=1;r<=n;r++)
                {
                    if (r==u || r==v) continue;
                    for (int i=1;i<=n;i++)
                    {
                        if (i==u || i==v) continue;
                        for (int j=1;j<=n;j++)
                        {
                            if (j==u || j==v) continue;
                            g[i][j]=(g[i][j]+f[i][r]*k[r][j]%mod)%mod;
                        }
                    }
                }
                for (int i=1;i<=n;i++)
                {
                    for (int j=1;j<=n;j++) f[i][j]=g[i][j];
                }
                d--;
//                for (int i=1;i<=n;i++)
//                {
//                    for (int j=1;j<=n;j++) cout<<f[i][j]<<" ";
//                    cout<<endl;
//                }
            }
            long long ret=0;
            for (int i=1;i<=n;i++)
            {
                for (int j=1;j<=n;j++)
                {
                    if (i!=u && i!=v && j!=u && j!=v) ret=(ret+(k[u][i] && k[j][v])*f[i][j]%mod)%mod;
                }
            }
            printf("%lld\n",ret);
        }
    }
}