#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

const int NAX = 3005;
vector<int> edges[NAX];

int n;

struct Info {
	int node;
	vector<int> nei;
};
vector<Info> history;
bitset<NAX> used;

void erase(int a) {
	debug() << "erase" imie(a);
	used[a] = 1;
	history.push_back(Info{a, edges[a]});
	for (int b : edges[a]) {
		edges[b].erase(find(edges[b].begin(), edges[b].end(), a));
	}
	edges[a].clear();
}

void cancel() {
	Info info = history.back();
	history.pop_back();
	int a = info.node;
	debug() << "cancel" imie(a);
	used[a] = 0;
	edges[a] = info.nei;
	for (int b : edges[a]) {
		edges[b].push_back(a);
	}
}

int max_remaining = -1;
bitset<NAX> possible;

void clear() {
	for (int i = 0; i <= n; i++) {
		edges[i].clear();
	}
	max_remaining = -1;
	possible = 0;
}

void consider(int r) {
	if (r > max_remaining) {
		max_remaining = r;
		possible = 0;
	}
	if (r == max_remaining) {
		debug() << "OK" imie(r);
		possible |= used;
	}
}

void rec(int k) {
	pair<int,int> big{0,0};
	for (int a = 0; a < n; a++) {
		big = max(big, {(int) edges[a].size(), a});
	}
	if (big.first == 0) {
		// no edges
		consider(k);
		max_remaining = max(max_remaining, k);
		return;
	}
	if (k == 0) {
		// you lost
		return;
	}
	
	// sort by degree decreasingly
	vector<int> freq(big.first+1);
	int all_edges = 0;
	for (int a = 0; a < n; a++) {
		if (!edges[a].empty()) {
			all_edges += edges[a].size();
			freq[edges[a].size()]++;
		}
	}
	int can_do = 0;
	int tmp = k;
	for (int i = big.first; i >= 1 && tmp > 0; i--) {
		int x = min(tmp, freq[i]);
		can_do += i * x;
		tmp -= x;
	}
	if (can_do < all_edges / 2) {
		return; // no way
	}
	
	if (big.first <= 2) {
		// paths & cycles
		vector<bool> visited(n);
		int required = 0;
		vector<bool> bad(n); // even positions in an odd path :(
		for (int start = 1; start <= 2; start++) {
			for (int a = 0; a < n; a++) {
				if (!visited[a] && (int) edges[a].size() == start) {
					vector<int> v;
					int prev = -1;
					int cur = a;
					while (!visited[cur]) {
						visited[cur] = true;
						v.push_back(cur);
						if (edges[cur][0] != prev) {
							prev = cur;
							cur = edges[cur][0];
						}
						else if ((int) edges[cur].size() == 2) {
							prev = cur;
							cur = edges[cur][1];
						}
						else {
							break;
						}
					}
					debug() << imie(start) imie(v);
					int size = v.size();
					if (start == 1) { // path
						required += size / 2;
						if (size % 2 == 1) {
							for (int i = 0; i < size; i += 2) {
								bad[v[i]] = true;
							}
						}
					}
					else { // cycle
						required += (size + 1) / 2;
					}
				}
			}
		}
		if (required <= k) {
			consider(k - required);
			if (k - required == max_remaining) {
				for (int i = 0; i < n; i++) {
					if (!edges[i].empty() && !bad[i]) {
						possible[i] = 1;
					}
				}
			}
		}
		return;
	}
	// node with degree >= 3
	int a = big.second;
	erase(a);
	rec(k-1);
	cancel();
	vector<int> others = edges[a];
	if (k < (int) others.size()) {
		return;
	}
	for (int b : others) {
		erase(b);
	}
	rec(k - (int) others.size());
	for (int rep = 0; rep < (int) others.size(); rep++) { // backwards
		cancel();
	}
}

void test_case() {
	int m, k;
	scanf("%d%d%d", &n, &m, &k);
	set<pair<int,int>> already;
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		if (already.count({a,b})) {
			continue;
		}
		already.insert({a,b});
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	rec(k);
	if (max_remaining == -1) {
		puts("-1");
	}
	else {
		printf("%d ", k - max_remaining);
		vector<int> those;
		for (int i = 0; i < n; i++) {
			if (possible[i]) {
				those.push_back(i+1);
			}
		}
		printf("%d\n", (int) those.size());
		for (int x : those) {
			printf("%d ", x);
		}
		puts("");
	}
	assert(history.empty() && used == 0);
	clear();
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		test_case();
	}
}