#include <bits/stdc++.h>
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
void solve() {
int msk[32];
for(int i = 0 ; i < 32 ; i++) {
msk[i] = 0;
msk[i] |= (1<<i);
}
int n, m; cin >> n >> m;
assert(n >= 1 and n <= 20);
assert(m >= 0 and m <= (n*(n-1))/2);
for(int i = 0 ; i < m ; i++) {
int u, v; cin >> u >> v;
assert(u >= 1 and u <= n);
assert(v >= 1 and v <= n);
u--, v--;
msk[u] |= (1<<v);
msk[v] |= (1<<u);
}
int ans = INF;
for(int i = 1 ; i < (1<<n) ; i++) {
int cur_mask = 0;
for(int cnt = 0 ; cnt < n ; cnt++) if(i&(1<<cnt)) cur_mask |= msk[cnt];
if(__builtin_popcount(cur_mask) == n) ans = min(ans, __builtin_popcount(i));
}
assert(ans >= 1 and ans <= n);
cout << ans << "\n";
}
int main() {
int t; cin >> t; while(t--) solve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgSU5GIDB4M2YzZjNmM2YKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgc29sdmUoKSB7CglpbnQgbXNrWzMyXTsKCWZvcihpbnQgaSA9IDAgOyBpIDwgMzIgOyBpKyspIHsKCQltc2tbaV0gPSAwOwoJCW1za1tpXSB8PSAoMTw8aSk7Cgl9CglpbnQgbiwgbTsgY2luID4+IG4gPj4gbTsKCWFzc2VydChuID49IDEgYW5kIG4gPD0gMjApOwoJYXNzZXJ0KG0gPj0gMCBhbmQgbSA8PSAobioobi0xKSkvMik7Cglmb3IoaW50IGkgPSAwIDsgaSA8IG0gOyBpKyspIHsKCQlpbnQgdSwgdjsgY2luID4+IHUgPj4gdjsKCQlhc3NlcnQodSA+PSAxIGFuZCB1IDw9IG4pOwoJCWFzc2VydCh2ID49IDEgYW5kIHYgPD0gbik7CgkJdS0tLCB2LS07CgkJbXNrW3VdIHw9ICgxPDx2KTsKCQltc2tbdl0gfD0gKDE8PHUpOwoJfQoKCWludCBhbnMgPSBJTkY7Cglmb3IoaW50IGkgPSAxIDsgaSA8ICgxPDxuKSA7IGkrKykgewoJCWludCBjdXJfbWFzayA9IDA7CgkJZm9yKGludCBjbnQgPSAwIDsgY250IDwgbiA7IGNudCsrKSBpZihpJigxPDxjbnQpKSBjdXJfbWFzayB8PSBtc2tbY250XTsKCQlpZihfX2J1aWx0aW5fcG9wY291bnQoY3VyX21hc2spID09IG4pIGFucyA9IG1pbihhbnMsIF9fYnVpbHRpbl9wb3Bjb3VudChpKSk7Cgl9CgoJYXNzZXJ0KGFucyA+PSAxIGFuZCBhbnMgPD0gbik7Cgljb3V0IDw8IGFucyA8PCAiXG4iOwp9CgppbnQgbWFpbigpIHsKCWludCB0OyBjaW4gPj4gdDsgd2hpbGUodC0tKSBzb2x2ZSgpOwp9