#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

#define F first
#define S second

const int MAXN = 9e3 + 10;
const int MOD = 1e9 + 7;

int n, k, m, q;
vector<int> adj[MAXN];
vector<pii> sec;

int place[MAXN];
bool fix(){
	sec.push_back({0, 0});
	sort(sec.begin(), sec.end());
	
	memset(place, -1, sizeof(place));
	for (auto x: sec){
		if (place[x.S] == -1)
			place[x.S] = x.F;
		else if (place[x.S] != x.F)
			return 1;
	}
	
	return 0;
}

void add(int &x, int y){
	x += y;
	while (x >= MOD) x -= MOD;
}

int d[2][MAXN];
int get(int st, int steps, int en = -1){
	memset(d, 0, sizeof(d));
	int cur = 0;
	d[cur][st] = 1;
	for (int i = 1; i <= steps; i++, cur ^= 1){
		memset(d[!cur], 0, sizeof(d[!cur]));
		for (int v = 0; v < n; v++) {
			for (int u:adj[v])
				add(d[!cur][u], d[cur][v]);
			add(d[!cur][v], d[cur][v]);
		}
	}
	
	if (~en)
		return d[cur][en];
	int ret = 0;
	for (int v = 0; v < n; v++)
		add(ret, d[cur][v]);
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		cin >> n >> m >> k;
		for (int i = 0; i < n; i++) adj[i].clear();
		while (m--){
			int a, b; cin >> a >> b, a--, b--;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}

		cin >> q;
		sec.clear();
		while (q--){
			int a, b; cin >> a >> b, a--;
			sec.push_back({a, b});
		}

		if (fix())
			cout << "0\n";
		else{
			int lst = 0, ans = 1, tm = 0;
			for (int i = 1; i <= k; i++)
				if (~place[i]){
					ans = 1ll*ans*get(lst, i - tm, place[i])%MOD;
					lst = place[i];
					tm = i;
				}
			if (tm^k)
				ans = 1ll*ans*get(lst, k-tm)%MOD;
			cout << ans << "\n";
		}
	}
	return 0;
}