#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define I inline
#define int long long
using namespace std;

const int mod = 1e9+7;
const int N = 400010;
int n,m,k,cnt;
int dep[N],pre[N],pw[N],c[N];
vector<int> q[N],v[N];

I void get(int x,int y) {
	if(dep[x]<dep[y]) return ;
	int mk=x; cnt++;
	while(1) {
		//cout<<mk<<' '<<pre[m]<<' '<<x<<' '<<y<<endl;
		v[cnt].push_back(mk);
		if(mk==y) return ;
		mk=pre[mk];
	}
}
void dfs1(int x,int fa) { //cout<<x<<' '<<fa<<endl;
	pre[x]=fa;
	dep[x]=dep[fa]+1;
	for(auto &t:q[x]) {
		if(t==fa) continue;
		if(dep[t]) get(x,t);
		else dfs1(t,x);	
	}
}
int qpow(int x,int y) {
	if(y==0) return 1;
	if(y==1) return x;
	int mk=qpow(x,y/2);
	return y%2?mk*mk%mod*x%mod:mk*mk%mod;
}
I void ycl() {
	pw[0]=1; cnt=0;
	for(int i=1;i<=n;++i) pw[i]=pw[i-1]*(k-1)%mod;
	for(int i=1;i<=n;++i) dep[i]=pre[i]=0,q[i].clear(),v[i].clear();
}
I void calc() {
	int inv=qpow(k,mod-2);
	c[3]=k*(k-1)%mod*(k-2)%mod;
	for(int i=4;i<=n;++i) {
		c[i]=k*pw[i-2]%mod*(k-2)%mod+k*(k-1)%mod*c[i-2]%mod*inv%mod;
		c[i]%=mod;
	}
}
I void check1() {
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;++i) {
		for(auto &t:v[i]) {
			cout<<t<<' ';
		} cout<<endl;
	}
}
I int read() {
	int ret=0,w=1; char ch;
	while((ch=getchar())>'9'||ch<'0'&&ch!='-'); if(ch=='-') w=-1; else ret=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
	return ret*w; 
}
signed main()
{
	int T; cin>>T;
	while(T--) {
		cin>>n>>m>>k; ycl();
		for(int i=1;i<=m;++i) {
			int x,y; x=read(); y=read();
			q[x].push_back(y);
			q[y].push_back(x);
		}
		dfs1(1,0); //check1();
		calc();
		int ans=1,sum=0;
		for(int i=1;i<=cnt;++i) {
			sum+=v[i].size(); 
			ans=ans*c[v[i].size()];
			ans%=mod;
		} //cout<<ans<<' '<<sum<<endl;
		if(!cnt) {
			ans=pw[n-1]*k%mod;
			cout<<ans<<endl;
			continue;
		}
		int inv=qpow(k,mod-2)*(k-1)%mod; //cout<<inv*
		ans=ans*qpow(inv,cnt-1)%mod;
		ans=ans*qpow(k-1,n-sum)%mod;
		cout<<ans<<endl;
	}
}
/*
	1
	6 7 3
	1 2
	2 3
	3 1
	4 5
	5 6
	6 4
	1 4

*/