#include <bits/stdc++.h> 
using namespace std;
const int maxn = 1e6+10;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int T;
int n,m,v;
int a,b;
struct node{
	int c,d;
}t[maxn];
int tg[maxn];
ll ans;
bool fl = false;
int p[maxn];
void dfs(int x){
	if(fl) return ;
	if(x == n+1){
		/*for(int i = 1; i <= n; i++){
			cout << tg[i] << " ";
		}
		cout << endl;*/
		for(int i = 1; i <= n; i++){
			if((tg[i] == a && tg[i+1] != b)){
				return ;
			}
			if(p[i]>0 && p[i] != tg[i]){
				return ;
			}
		}
		fl = true;
		return ;
	}
	if(tg[x] > 0) dfs(x+1);
	for(int i = 1; i <= v; i++){
		tg[x] = i;
		dfs(x+1);
		tg[x] = 0;
	}
}
int main(){
	//edit assign traverse query
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin >> T;
	while(T--){
		ans = 0;
		memset(tg,0,sizeof(tg));
		memset(p,0,sizeof(p));
		cin >> n >> m >> v;
		for(int i = 1; i <= m; i++){
			cin >> t[i].c >> t[i].d;
			tg[t[i].c] = t[i].d;
			p[t[i].c] = t[i].d;
		}
		for(int i =1; i <= n; i++){
			cout << p[i] << " ";
		}
		cout << endl;
		for(a = 1; a <= v; a++){
			for(b = 1; b <= v; b++){
				fl = false;
				//cout << "*" <<a << " " << b << " ";
				dfs(1);
				if(fl) ans++;
				cout << fl << endl;
			}
		}
		cout << ans%mod << endl;
	}
	return 0;
}
