//树上差分(LCA)

 #include<bits/stdc++.h>

 #define For(i,x,y) for (int i=x;i<y;i++)

 #define fi first

 #define se second

 #define pb push_back

 #define mp make_pair

 #define lf else if

 #define dprintf(...) fprintf(stderr,__VA_ARGS__)

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 typedef vector<int> Vi;

 int IN(){//读入挂

     int c,f,x;

     while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=,x=):(f=,x=c-'');

     while (isdigit(c=getchar())) x=(x<<)+(x<<)+c-'';return !f?x:-x;

 }

 const int p=1e9+;

 const int N=3e5+;

 int Pow(int a,int b){//快速幂

     int res=;

     for (;b;b>>=,a=1ll*a*a%p) if (b&) res=1ll*res*a%p;

     return res;

 }

 struct Edge{

     int y,nxt;

 } E[N*];

 int fac[N],inv[N];

 int las[N],fa[][N],A[N],B[N],dep[N];

 int n,m,cnt,x,y,z,ans,k;

 int C(int n,int m){//组合数

     if (n<m) return ;

     return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;

 }

 void Link(int x,int y){//链式前向星存图

     E[cnt]=(Edge){y,las[x]};las[x]=cnt++;

     E[cnt]=(Edge){x,las[y]};las[y]=cnt++;

 }

 void dfs(int x){//LCA的dfs

     for (int i=las[x],y;~i;i=E[i].nxt)

         if ((y=E[i].y)!=fa[][x]){

             fa[][y]=x;

             dep[y]=dep[x]+;

             dfs(y);

         }

 }

 int LCA(int x,int y){//LCA(ST)

     if (dep[x]>dep[y]) swap(x,y);

     for (int i=dep[y]-dep[x],k=;i;i>>=,k++) if(i&) y=fa[k][y];

     if(x==y) return x;

     for (int i=;~i;i--) if (fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];

     return fa[][x];

 }

 void Dfs(int x){//树上差分的dfs，从根节点深搜，回溯时将其本身的权值加上所有子节点的权值

     for (int i=las[x],y;~i;i=E[i].nxt)

         if ((y=E[i].y)!=fa[][x]){//筛掉父节点

             Dfs(y);

             A[x]+=A[y];//累加权值和

             B[x]+=B[y];

         }

 }

 void Main(){

     n=IN(),m=IN(),k=IN();

     For(i,,n+) las[i]=-,A[i]=B[i]=;

     cnt=;

     For(i,,n) Link(IN(),IN());

     dfs();

     For(i,,) For(x,,n+) fa[i][x]=fa[i-][fa[i-][x]];

     For(i,,m+){

         x=IN(),y=IN();

         z=LCA(x,y);

         A[x]++,A[y]++,A[z]--,A[fa[][z]]--;

         B[x]++,B[y]++,B[z]-=;//起点终点权值+1，lca权值-2

     }

     Dfs();

     ans=;

 //    cout<<"--------"<<endl;

 //    for(int i=1;i<=n;i++)

 //        cout<<i<<" "<<A[i]<<endl;

 //    cout<<"--------"<<endl;

 //    for(int i=2;i<=n;i++)

 //        cout<<i<<" "<<B[i]<<endl;

 //    cout<<"--------"<<endl;

     For(i,,n+){

         ans=(ans+C(A[i],k))%p;

     }

     For(i,,n+){

         ans=(ans-C(B[i],k)+p)%p;

     }

     printf("%d\n",ans);

 }

 int main(){

     fac[]=;

     For(i,,N) fac[i]=1ll*fac[i-]*i%p;

     inv[N-]=Pow(fac[N-],p-);

     for(int i=N-;i;i--) inv[i-]=1ll*inv[i]*i%p;

     for(int T=IN();T--;) Main();

 }

 /*

 1

 3 6 2

 1 2

 1 3

 1 1

 2 2

 3 3

 1 2

 1 3

 2 3

 */