#include <cassert>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAXN = 500;
 
int Tn, n, m, x, y, wn, wx[MAXN], wy[MAXN], c[MAXN], k1, k2, k3;
 
int main (int argc, char * const argv[]) {
	cin >> Tn;
	assert(1 <= Tn && Tn <= 20);
	while (Tn--) {
		cin >> n >> m;
		assert(1 <= n && n <= 100);
		assert(n - 1 <= m && m <= n * (n - 1) / 2);
		if (n == 1) {
			cout << "0 0" << endl;
			continue;
		}
		if (n == 2) {
			cin >> x >> y;
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
			cout << "0 0" << endl;
			continue;
		}
		if (n == 3 && m == 3) {
			cin >> x >> y;
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
			cin >> x >> y;
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
			cin >> x >> y;
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
			cout << "0 0" << endl;
			continue;
		}
		if (n == 3 && m == 2) {
			for(int i = 1; i <= n; i++)
				c[i] = 0;
			cin >> x >> y;
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
			++c[x];
			++c[y];
			cin >> x >> y;
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
			++c[x];
			++c[y];
			for(int i = 1; i <= n; i++)
				if (c[i] == 2)
					k2 = i;
				else
					k1 = i;
			for(int i = 1; i <= n; i++) if (k1 != i && k2 != i)
				k3 = i;
			cout << "4 6" << endl;
			cout << k1 << " 4" << endl;
			cout << k1 << " 5" << endl;
			cout << k2 << " 6" << endl;
			cout << k2 << " 7" << endl;
			cout << k3 << " 4" << endl;
			cout << k3 << " 5" << endl;
			continue;
		}
		for(int i = 0; i < m; i++) {
			cin >> x >> y;		
			assert(1 <= x && x <= n);
			assert(1 <= y && y <= n);
			assert(x != y);
		}
		wn = 0;
		for(int i = 1; i <= n; i++) {
			++wn;
			wx[wn] = n + 1;
			wy[wn] = i;
		}
		for(int i = 1; i <= n; i++) {
			++wn;
			wx[wn] = i;
			wy[wn] = n + 2;			
		}
		++wn;
		wx[wn] = n + 1;
		wy[wn] = n + 3;
		++wn;
		wx[wn] = n + 2;
		wy[wn] = n + 4;
		cout << 4 << " " << wn << endl;
		for(int i = 1; i <= wn; i++)
			cout << wx[i] << " " << wy[i] << endl;
	}
    return 0;
}