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
121
122
123
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1010, M = 3030;
int n, m, k, deg[N], use[N], ok[N];
int ans, flag;
vector<int> G[N];
void del(int u) {
	use[u] = 1;
	for(auto v : G[u]) deg[v] --;
}
void add(int u) {
	use[u] = -1;
	for(auto v : G[u]) deg[v] ++;
}
void dfs(int k) {
	if(k > ans) return ;
	int mx = 0, p = -1;
	for(int i = 1; i <= n; i ++) if(!~use[i] && deg[i]) {
		if(deg[i] > mx) mx = deg[i], p = i;
	}
	if(mx <= 2) {
		static int last[N];
		memcpy(last, use, n + 1 << 2);
		static int vis[N], ts = 0, sum[N];
		ts ++;
		for(int i = 1; i <= n; i ++) if(!~last[i] && deg[i] && vis[i] != ts) {
			static int que[N], hh, tt;
			que[hh = 1] = i; tt = 1;
			vis[i] = ts; 
			int _n = 0, _m = 0;
			while(hh <= tt) {
				int u = que[hh ++];
				_n ++; sum[u] = 0;
				for(auto v : G[u]) if(!~use[v]) {
					if(vis[v] != ts) que[++ tt] = v, vis[v] = ts;
					_m ++; sum[u] += v;
				}
			}
			_m >>= 1;
			if(_n == _m) {
				k += _n + 1 >> 1;
				for(int i = 1; i <= _n; i ++) {
					use[que[i]] = 1;
				}
			} else {
				assert(_m == _n - 1);
				k += _n >> 1;
				if(_n & 1) {
					int p = -1;
					for(int i = 1; i <= _n; i ++) if(deg[que[i]] == 1) p = que[i];
					for(int i = 1, q = 0, tmp; i <= _n; i ++, tmp = q, q = p, p = sum[p] - tmp) {
						if(1 + i & 1) use[p] = 1;
					}
				} else {
					for(int i = 1; i <= _n; i ++) {
						use[que[i]] = 1;
					}
				}
			}
		}
		if(k == ans) {
			flag = 1;
			for(int i = 1;i <= n; i ++) ok[i] = use[i] == 1 ? 1 : ok[i];
		} else if(k < ans) {
			ans = k; flag = 1;
			for(int i = 1; i <= n; i ++) ok[i] = use[i] == 1 ? 1 : 0;
		}
		memcpy(use, last, n + 1 << 2);
		return ;
	}
	if(p == -1) {
		flag = 1;
		if(k == ans) {
			for(int i = 1; i <= n; i ++) ok[i] = use[i] == 1 ? 1 : ok[i];
		} else {
			ans = k;
			for(int i = 1; i <= n; i ++) ok[i] = use[i] == 1 ? 1 : 0;
		}
		return ;
	}
	del(p);
	dfs(k + 1);
	use[p] = 0;
	vector<int> t;
	for(auto v : G[p]) if(!~use[v]) del(v), t.emplace_back(v);
	dfs(k + t.size());
	add(p);
	for(auto v : t) add(v);
}
void solve() {
	cin >> n >> m >> k;
	fill(use + 1, use + n + 1, 0);
	for(int i = 1; i <= m; i ++) {
		int u, v;
		cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		deg[u] ++, deg[v] ++;
		use[u] = use[v] = -1;
	}
	ans = k, flag = 0;
	dfs(0);
	if(flag) {
		cout << ans << ' ' << accumulate(ok + 1, ok + n + 1, 0) << '\n';
		for(int i = 1; i <= n; i ++) if(ok[i]) cout << i << ' ';
		cout << '\n';
	} else {
		cout << -1 << '\n';
	}
}
void clear() {
	for(int i = 1; i <= n; i ++) ok[i] = deg[i] = 0, use[i] = -1, G[i].clear();
}
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	for(cin >> T; T; T --) {
		solve();
		clear();
	}
	return 0;
}