#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],f[N],g[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);
	g[1]=0; f[1]=k; f[2]=k*(k-1)%mod; f[3]=k*(k-1)%mod*(k-2)%mod; g[3]=f[3];
	for(int i=4;i<=n;++i) {
		f[i]=(k-1)*f[i-2]%mod+g[i-1]*(k-2)%mod;
		f[i]=(f[i]>=mod?f[i]-mod:f[i]);
		g[i]=(k-1)*f[i-2]%mod+(k-2)*g[i-1]%mod;
		g[i]=(g[i]>=mod?g[i]-mod:g[i]);
	}
}
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); //cout<<"sasa"; check1();
		calc();
	//	for(int i=1;i<=n;++i) cout<<f[i]<<' '; cout<<endl;
		int ans=1,sum=0;
		for(int i=1;i<=cnt;++i) {
			sum+=v[i].size(); 
			ans=ans*f[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;
	}
}
/*
2
9 10 4
4 7
5 2
1 5
7 3
9 6
8 3
3 2
9 1
4 8
6 2

8 9 2
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 5
1 8
*/