1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
int zaklecia[3010][2];
int it = 0;
int wystapienia[1010][2];
int ile[1010];
int order[1010];
vector<vector<int>>wygenerowane;
vector<int>pom;
bool czy[1010];
void generuj(int a, int k, int n)
{
	if(a == k || a==n){
		wygenerowane.push_back(pom);
		return;
	}
	for(int i=1;i<=n;i++){
		if(czy[i]==0){
			pom.push_back(i);
			czy[i] = 1;
			generuj(a+1, k, n);
			czy[i] = 0;
			pom.pop_back();
		}
	}
}

void solve(){
	int n, m, k, i=0;
	scanf("%d%d%d", &n, &m, &k);
	wygenerowane.clear();
	generuj(0, k, n);
	for(i=0;i<m;i++)
		scanf("%d%d", &zaklecia[i][0], &zaklecia[i][1]);
	vector<int>perm;
	for(i=1;i<=n;i++)
	{
		perm.push_back(i);
		order[i] = 1000;
		ile[i] = 1000;
	}
	int rekord = 1000;
	//int it=0;
	for(auto perm: wygenerowane){
		//if(++it%1000000==0)
		//	printf("liczy sie %d\n", it);
		for(i=1;i<=min(n, k);i++)
			order[perm[i-1]] = i;
		int rek = 0;
		for(i=0;i<m;i++){
			rek = max(rek, min(order[zaklecia[i][0]], order[zaklecia[i][1]]));
			if(rek>k)
				break;
		}
		rekord = min(rekord, rek);
		for(i=1;i<=min(n, k);i++){
			if(i<=rek)
				ile[perm[i-1]] = min(ile[perm[i-1]], rek);
			order[perm[i-1]] = 1000;
		}
	}
	if(rekord<=k){
		vector<int>zlicz;
		for(i=1;i<=n;i++)
			if(ile[i] == rekord)
				zlicz.push_back(i);
		printf("%d %d\n", rekord, (int)zlicz.size());
		for(auto j: zlicz)printf("%d ", j);
	}
	else
		printf("-1");
	printf("\n");
}
int main()
{
	int t;
	scanf("%d", &t);
	while(t--){
		solve();
	}
}