#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
struct mat {
mat(int dim)
: n(dim) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = 0.0;
}
int findMaxInColumn(int c) {
int max = c;
for (int i = c + 1; i < n; i++)
if (fabs(d[i][c]) > fabs(d[max][c]))
max = i;
return max;
}
void swapRow(int r1, int r2) {
for (int j = 0; j < n; j++)
std::swap(d[r1][j], d[r2][j]);
}
bool gaussian() {
for (int i = 0; i < n; i++) {
int m = findMaxInColumn(i);
if (m != i)
swapRow(i, m);
if (fabs(d[i][i]) < 1e-9)
return false;
for (int j = i + 1; j < n; j++) {
double q = d[j][i] / d[i][i];
for (int k = i; k < n; k++)
d[j][k] -= q * d[i][k];
d[j][i] = 0;
}
}
return true;
}
double determinant() {
double det = 1;
for (int i = 0; i < n; i++)
det *= d[i][i];
return det;
}
void dump() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%lf ", d[i][j]);
printf("\n");
}
}
int n;
double d[100][100];
};
struct edge {
int a, b;
};
int main(int argc, char* argv[]) {
srand(time(NULL));
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d %d", &n, &m);
std::vector<edge> edges;
for (int i = 0; i < m; i++) {
edge e;
scanf("%d %d", &e.a, &e.b);
e.a--; e.b--;
edges.push_back(e);
}
bool pm = false;
if ((n % 2) == 0) {
// || (m < (n / 2))
// || (n > 50)) {
for (int k = 0; k < 10; k++) {
mat mtx(n);
for (unsigned int i = 0; i < edges.size(); i++) {
const edge& e = edges[i];
int v = rand() % 1000000007;
mtx.d[e.a][e.b] = v; mtx.d[e.b][e.a] = -v;
}
if (mtx.gaussian()) {
// && (fabs(mtx.determinant()) > 1e-9)) {
pm = true;
break;
}
mtx = mat(n);
}
}
printf(pm ? "YES\n" : "NO\n");
}
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3N0cmluZz4KCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CgpzdHJ1Y3QgbWF0IHsKICAgbWF0KGludCBkaW0pCiAgICAgIDogbihkaW0pIHsKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKQogICAgICAgICAgICBkW2ldW2pdID0gMC4wOwogICB9CgogICBpbnQgZmluZE1heEluQ29sdW1uKGludCBjKSB7CiAgICAgIGludCBtYXggPSBjOwogICAgICBmb3IgKGludCBpID0gYyArIDE7IGkgPCBuOyBpKyspCiAgICAgICAgIGlmIChmYWJzKGRbaV1bY10pID4gZmFicyhkW21heF1bY10pKQogICAgICAgICAgICBtYXggPSBpOwogICAgICByZXR1cm4gbWF4OwogICB9CgogICB2b2lkIHN3YXBSb3coaW50IHIxLCBpbnQgcjIpIHsKICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspCiAgICAgICAgIHN0ZDo6c3dhcChkW3IxXVtqXSwgZFtyMl1bal0pOwogICB9CgogICBib29sIGdhdXNzaWFuKCkgewogICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICBpbnQgbSA9IGZpbmRNYXhJbkNvbHVtbihpKTsKCiAgICAgICAgIGlmIChtICE9IGkpCiAgICAgICAgICAgIHN3YXBSb3coaSwgbSk7CgogICAgICAgICBpZiAoZmFicyhkW2ldW2ldKSA8IDFlLTkpCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKCiAgICAgICAgIGZvciAoaW50IGogPSBpICsgMTsgaiA8IG47IGorKykgewogICAgICAgICAgICBkb3VibGUgcSA9IGRbal1baV0gLyBkW2ldW2ldOwogICAgICAgICAgICBmb3IgKGludCBrID0gaTsgayA8IG47IGsrKykKICAgICAgICAgICAgICAgZFtqXVtrXSAtPSBxICogZFtpXVtrXTsKICAgICAgICAgICAgZFtqXVtpXSA9IDA7CiAgICAgICAgIH0KICAgICAgfQoKICAgICAgcmV0dXJuIHRydWU7CiAgIH0KCiAgIGRvdWJsZSBkZXRlcm1pbmFudCgpIHsKICAgICAgZG91YmxlIGRldCA9IDE7CiAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgICBkZXQgKj0gZFtpXVtpXTsKICAgICAgcmV0dXJuIGRldDsKICAgfQoKICAgdm9pZCBkdW1wKCkgewogICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IG47IGorKykKICAgICAgICAgICAgcHJpbnRmKCIlbGYgIiwgZFtpXVtqXSk7CiAgICAgICAgIHByaW50ZigiXG4iKTsKICAgICAgfQogICB9CgogICBpbnQgICAgIG47CiAgIGRvdWJsZSAgZFsxMDBdWzEwMF07Cn07CgpzdHJ1Y3QgZWRnZSB7CiAgIGludCBhLCBiOwp9OwoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqIGFyZ3ZbXSkgewogICBzcmFuZCh0aW1lKE5VTEwpKTsKCiAgIGludCB0OwogICBzY2FuZigiJWQiLCAmdCk7CiAgIHdoaWxlICh0LS0pIHsKICAgICAgaW50IG4sIG07CiAgICAgIHNjYW5mKCIlZCAlZCIsICZuLCAmbSk7CgogICAgICBzdGQ6OnZlY3RvcjxlZGdlPiBlZGdlczsKICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKICAgICAgICAgZWRnZSBlOwogICAgICAgICBzY2FuZigiJWQgJWQiLCAmZS5hLCAmZS5iKTsKICAgICAgICAgZS5hLS07IGUuYi0tOwogICAgICAgICBlZGdlcy5wdXNoX2JhY2soZSk7CiAgICAgIH0KCiAgICAgIGJvb2wgcG0gPSBmYWxzZTsKICAgICAgaWYgKChuICUgMikgPT0gMCkgewogICAgICAgICAvLyB8fCAobSA8IChuIC8gMikpCiAgICAgICAgIC8vIHx8IChuID4gNTApKSB7CiAgICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgMTA7IGsrKykgewogICAgICAgICAgICBtYXQgbXR4KG4pOwogICAgICAgICAgICBmb3IgKHVuc2lnbmVkIGludCBpID0gMDsgaSA8IGVkZ2VzLnNpemUoKTsgaSsrKSB7CiAgICAgICAgICAgICAgIGNvbnN0IGVkZ2UmIGUgPSBlZGdlc1tpXTsKICAgICAgICAgICAgICAgaW50IHYgPSByYW5kKCkgJSAxMDAwMDAwMDA3OwogICAgICAgICAgICAgICBtdHguZFtlLmFdW2UuYl0gPSB2OyBtdHguZFtlLmJdW2UuYV0gPSAtdjsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKG10eC5nYXVzc2lhbigpKSB7CiAgICAgICAgICAgIC8vICYmIChmYWJzKG10eC5kZXRlcm1pbmFudCgpKSA+IDFlLTkpKSB7CiAgICAgICAgICAgICAgIHBtID0gdHJ1ZTsKICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIG10eCA9IG1hdChuKTsKICAgICAgICAgfQogICAgICB9CgogICAgICBwcmludGYocG0gPyAiWUVTXG4iIDogIk5PXG4iKTsKICAgfQoKICAgcmV0dXJuIDA7Cn0K