#include <bits/stdc++.h>
using namespace std;
long long int n=0,m=0,z=0,a=0,b=0,q=0,u[500001]={},v[500001]={},d[500001]={},num[500001]={},road[101][101]={},jz[51][101][101]={};
int main()
{
 freopen("messenger.in","r",stdin);
 freopen("messenger.out","w",stdout);
 cin>>n>>m>>z;
 for(int i=1;i<=m;i++)
 {
  cin>>a>>b;
  road[a][b]++;
 }
 cin>>q;
 for(int i=1;i<=q;i++)
 {
  cin>>u[i]>>v[i]>>d[i];
 }
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {
   jz[1][i][j]=road[i][j];
  }
 for(int i=2;i<=50;i++)
  for(int j=1;j<=n;j++)
   for(int t=1;t<=n;t++)
    for(int r=1;r<=n;r++)
    {
     jz[i][j][t]=jz[i][j][t]+jz[i-1][j][r]*road[r][t];
     
    }
 for(int i=1;i<=q;i++)
 {
  num[i]=jz[d[i]][u[i]][v[i]];
  for(int j=1;j<d[i];j++)
  num[i]=num[i]-jz[j][u[i]][u[i]]*jz[d[i]-j][u[i]][v[i]];
  for(int j=1;j<d[i];j++)
  num[i]=num[i]-jz[j][u[i]][v[i]]*jz[d[i]-j][v[i]][v[i]];
  cout<<num[i]<<endl;
 }
 
 
 
 
 
}