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
#include <cstdio>
#include <vector>
#include <cassert>
#include <bitset>

const int N = 6000;
using magia = std::bitset<N>;

int t, n, m, k;
magia g[N];
int ans;
magia ans_mask;
void dfs(int c, magia select, magia alive) {
    if (c > k || c > ans) return;
    int mx = -1, mxDeg = -1;
    for (int i = alive._Find_first(); i < n; i = alive._Find_next(i)) {
        int deg = (alive & g[i]).count();
        if (deg == 1) {
            int j = (alive & g[i])._Find_first();
            alive[i] = alive[j] = false;
            select[j] = true;
            dfs(c+1, select, alive);
            return;
        }
        if (deg && deg > mxDeg)
            mx = i, mxDeg = deg;
    }
    if (mx == -1) {
        if (ans > c) {
            ans = c;
            ans_mask = select;
        } else {
			assert(ans == c);
			ans_mask |= select;
		}
        return;
    }
    alive[mx] = false;
    select[mx] = true;
    dfs(c + 1, select, alive);
    select[mx] = false;
    magia adj = alive & g[mx];
    dfs(c+adj.count(), select | adj, alive ^ adj);
}
signed main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &k);
		for(int i = 0; i < m; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			--a;
			--b;
			g[a][b] = g[b][a] = true;
		}
		ans = k + 1;
		magia select, alive;
		for(int i = 0; i < n; i++) alive[i] = true;
		dfs(0, select, alive);
		if (ans != k + 1) for (int i = 0; i < n; ++i) if (!ans_mask[i]) {
			alive[i] = false;
			select[i] = true;
			dfs(1, select, alive);
			alive[i] = true;
			select[i] = false;
		}
		if (ans == k + 1) printf("-1\n");
		else {
			std::vector<int> odp;
			for (int i = 0; i < n; ++i) if (ans_mask[i]) odp.push_back(i);
			printf("%d %d\n", ans, (int)odp.size());
			for (int i = 0; i < (int)odp.size(); ++i) printf("%d ", odp[i] + 1);
			printf("\n");
		}
		for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) g[i][j] = 0;
		ans_mask = magia();
	}
	return 0;
}