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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>

using namespace std;

bool findCover(int k, int m, vector<vector<int>>& g, vector<int>& deg, vector<bool>& used){
	if(m == 0)return true;//juz pokryte wszystkie krawedzi
	int maxDeg = 0;
	int v = -1;
	for(int i= 0; i < deg.size(); i++){
		if(!used[i] && deg[i] > maxDeg){
			maxDeg = deg[i];
			v = i;
		}
	}
	if(maxDeg * k < m)return false;
	//teraz dodajemy goscia
	used[v] = true;
	for(auto u : g[v])deg[u]--;
	bool magic = findCover(k-1, m - deg[v], g, deg, used);
	used[v] = false;
	for(auto u : g[v])deg[u]++;
	if(magic)return true;
	//bierzemy wszyskich sasiadow zamiast goscia
	if(deg[v] <= k){
		vector<int> t;
		for(auto u : g[v]){
			if(!used[u]){
				t.push_back(u); 
				//used[u] = true;
			}
		}
		for(auto u : t){
			used[u] = true;
			for(auto w : g[u]){
				deg[w]--;
				if(!used[w]){
					m--;
				}
			}
		}
		magic = findCover(k-t.size(), m, g, deg, used);
		for(auto u : t){
			used[u] = false;
			for(auto w : g[u]){
				deg[w]++;
			}
		}
		if(magic){
			//cout<<"To jest sus\n";
			return true;
		}
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n, m, k; cin>>n>>m>>k;
		//if(n >= 900 && m >= 2000 && k >= 25)cout<<"Yay\n";
		vector<vector<int>> g(n);
		vector<int> deg(n, 0);
		vector<bool> used(n, false);
		vector<vector<bool>> edgeUsed(n, vector<bool>(n, false));
		int realM = 0;
		for(int i= 0; i < m; i++){
			int a, b; cin>>a>>b; a--; b--;
			if(!edgeUsed[a][b]){
				realM++;
				edgeUsed[a][b] = true;
				deg[a]++; deg[b]++;
				g[a].push_back(b);
				g[b].push_back(a);
			}
		}
		int l = 1; int r = k +1;
		while(l < r){
			int middle = (l + r) / 2;
			if(!findCover(middle, realM, g, deg, used)){
				l = middle + 1;
			}else{
				r = middle;
			}
		}
		if(r == k+1){
			cout<<"-1\n";
		}else{
			vector<int> special;
			for(int i= 0; i < n; i++){
				used[i] = true;
				for(auto u : g[i]){
					deg[u]--;
				}
				realM -= deg[i];
				if(findCover(l-1, realM, g, deg, used))special.push_back(i+1);
				realM += deg[i];
				used[i] = false;
				for(auto u : g[i])deg[u]++;
			}
			// w szczegolnosci special powinien byc jakims coverem, mozna to sprawdzic
			/*int coverCnt = 0;
			for(auto x : special){
				x--;
				used[x] = true;
				for(auto u : g[x]){
					if(!used[u]){
						coverCnt++;
					}
				}
			}
			if(coverCnt < m)cout<<"Cos nie dziala mi cover XD\n";*/
			cout<<l<<" "<<special.size()<<"\n";
			for(auto x : special)cout<<x<<" ";
			cout<<"\n";
		}
	}
}