sumOfCubes.cpp

#include <bits/stdc++.h>

using namespace std;

int main(void) {

	int t; cin >> t;
	while (t--) {
		int n, e, k;
		cin >> n >> e >> k;

		vector< vector<int> > adjList(n);
		int degree[n] = {0};

		for (int i = 0,x,y; i < e; i++) {
			cin >> x >> y;
			x--; y--;
			adjList[x].push_back(y);
			adjList[y].push_back(x);
			degree[x]++; degree[y]++;
		}

		long long sum = 0;

		for (int i = 3; i < (1 << n); i++) {
			int temp[n];
			for (int l = 0; l < n; l++) temp[l] = degree[l];

			int j = i;
			int idx = 0;
			int currBit = 0;

			while (currBit < n) {
				if ((j >> currBit) & 1 == 1) {
					
				} else {
					temp[idx] = 0;
					for (int l = 0; l < adjList[idx].size(); l++) {
						if (temp[adjList[idx][l]] > 0) temp[adjList[idx][l]]--;
						temp[idx] = 0;
					}
				}

				idx++; currBit++;
			}

			int currSum = 0;

			for (int i = 0; i < n; i++) currSum += temp[i];

			currSum = currSum / 2;
			sum += pow(currSum, k);
		}

		cout << sum << endl;
	}
	

	return 0;
}