#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1012345678;

struct edge {
	int t, cap, rev;
};

void add_edge(vector<vector<edge> >& G, int a, int b, int c) {
	G[a].push_back(edge{b, c, int(G[b].size())});
	G[b].push_back(edge{a, 0, int(G[a].size()) - 1});
}

int dinic(int V, vector<vector<edge> >& G, int S, int T) {
	int flow = 0;
	while (true) {
		// calculate level
		vector<int> d(V, -1);
		d[S] = 0;
		queue<int> que;
		que.push(S);
		while (!que.empty()) {
			int u = que.front();
			que.pop();
			for (edge e : G[u]) {
				if (e.cap > 0 && d[e.t] == -1) {
					d[e.t] = d[u] + 1;
					que.push(e.t);
				}
			}
		}
		if (d[T] == -1) {
			break;
		}
		// make flow
		vector<int> counter(T);
		auto dfs = [&](auto& self, int x, int cur) -> int {
			if (x == T) {
				return cur;
			}
			while (counter[x] != int(G[x].size())) {
				edge& e = G[x][counter[x]++];
				if (d[e.t] - d[x] == 1 && e.cap > 0) {
					int res = self(self, e.t, min(cur, e.cap));
					if (res > 0) {
						e.cap -= res;
						G[e.t][e.rev].cap += res;
						return res;
					}
				}
			}
			return 0;
		};
		while (true) {
			int subflow = dfs(dfs, S, INF);
			if (subflow == 0) {
				break;
			}
			flow += subflow;
		}
	}
	return flow;
}

pair<int, vector<int> > solve(int N, const vector<vector<int> >& G) {
	// step #1. warshall-floyd
	vector<vector<int> > d(N, vector<int>(N, INF));
	for (int i = 0; i < N; i++) {
		d[i][i] = 0;
	}
	for (int i = 0; i < N; i++) {
		for (int j : G[i]) {
			d[i][j] = 1;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}

	// step #2. make flow graph
	vector<vector<edge> > H(2 * N + 2);
	for (int i = 0; i < N; i++) {
		add_edge(H, i, N + i, 1);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (d[i][j] <= 3) {
				add_edge(H, N + i, j, INF);
			}
			if (d[0][i] <= 2) {
				add_edge(H, N * 2 + 0, i, INF);
			}
			if (d[i][N - 1] <= 2) {
				add_edge(H, N + i, N * 2 + 1, INF);
			}
		}
	}
	add_edge(H, N * 2 + 0, 0, INF);
	add_edge(H, N + (N - 1), N * 2 + 1, INF);

	// step #3. compute answer
	int flow = dinic(N * 2 + 2, H, N * 2, N * 2 + 1);
	vector<bool> vis(N * 2 + 2, false);
	auto dfs = [&](auto& self, int x) -> void {
		vis[x] = true;
		for (edge e : H[x]) {
			if (e.cap > 0 && !vis[e.t]) {
				self(self, e.t);
			}
		}
	};
	dfs(dfs, N * 2 + 0);
	vector<bool> cut(N, false);
	for (int i = 0; i < N; i++) {
		cut[i] = (vis[i] && !vis[N + i]);
	}
	vector<int> v;
	for (int i = 0; i < N; i++) {
		if (cut[i] && i != 0 && i != N - 1) {
			bool f = true;
			for (int j : G[i]) {
				if (!cut[j]) {
					f = false;
				}
			}
			if (f) {
				v.push_back(i);
			}
		}
	}
	return {flow, v};
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int id = 1; id <= T; id++) {
		int N, M;
		cin >> N >> M;
		vector<vector<int> > G(N);
		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		auto [cnt, v] = solve(N, G);
		cout << cnt << ' ' << v.size() << endl;
		for (int i = 0; i < int(v.size()); i++) {
			if (i != 0) {
				cout << ' ';
			}
			cout << v[i] + 1;
		}
		cout << endl;
	}
	return 0;
}