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
#include <bits/stdc++.h>
using namespace std;
const int N = 3007;
vector<int> G[N];
vector<vector<int> > edges;
const int INF = 1e9+7;
bool vis[N];
int n,m,k;
int lim = INF,mi[N];
int calc(int curdepth){
	bool flag = 1;
	int cnt = 0;
	for(int i = 0;i<m;i+=1){
		if (!vis[i]){
			flag = 0;
			cnt += 1;
		}
	}
	if (curdepth>lim || curdepth>k){
		return INF;
	}
	if (flag){
		lim = min(lim,curdepth);
		return curdepth;
	}
	int ret = INF;
	vector<int> V;
	for(int i = 1;i<=n;i+=1){
		int cd = 0;
		for(int to:G[i]){
			cd += !vis[to];
		}
		if (cd){
			V.push_back(cd);
		}
	}
	sort(V.begin(),V.end());
	int sum = 0;
	for(int i = int(V.size())-1,j = 0;i>=0 && j<k-curdepth+1;j+=1){
		sum += V[i];
	}
	if (sum<cnt){
		return INF;
	}
	for(int i = 0;i<m;i+=1){
		if (vis[i]){
			continue;
		}
		for(int nxt:edges[i]){
			vector<int> cl;
			for(int to:G[nxt]){
				if (vis[to]==0){
					vis[to] = 1;
					cl.push_back(to);
				}
			}
			int cur = calc(curdepth+1);
			mi[nxt] = min(mi[nxt],cur);
			ret = min(ret,cur);
			for(int to:cl){
				vis[to] = 0;
			}
		}
		break;
	}
	return ret;
}
int deg[N];
bool mc(vector<int> &a,vector<int> &b){
	return deg[a[0]]+deg[a[1]]<deg[b[0]]+deg[b[1]];
}
void solve(){
	lim = INF;
	cin>>n>>m>>k;
	edges.clear();
	for(int i = 1;i<=n;i+=1){
		G[i].clear();
		mi[i] = INF;
		deg[i] = 0;
	}
	for(int i = 0;i<m;i+=1){
		int u,v;
		cin>>u>>v;
		deg[u] += 1;
		deg[v] += 1;
		edges.push_back(vector<int>{u,v});
	}
	sort(edges.begin(),edges.end(),mc);
	reverse(edges.begin(),edges.end());
	for(int i = 0;i<m;i+=1){
		G[edges[i][0]].push_back(i);
		G[edges[i][1]].push_back(i);
	}
	int depth = calc(0);
	if (depth==INF){
		cout<<"-1\n";
		return;
	}
	vector<int> ans;
	for(int i = 1;i<=n;i+=1){
		int cur = mi[i];
		if (cur==depth || G[i].size()==m){
			ans.push_back(i);
		}
	}
	cout<<depth<<' '<<ans.size()<<endl;
	for(int to:ans){
		cout<<to<<' ';
	}
	cout<<endl;
}
signed main(){
	int tt;
	cin>>tt;
	while(tt--){
		solve();
	}
}