P1006

#include <bits/stdc++.h>

const int N = 400010, M = 800010;
int t, n, m;
int head[N], nxt[M << 1], to[M << 1], idx;
int color[N];

void add(int u, int v) {
    nxt[idx] = head[u];
    to[idx] = v;
    head[u] = idx;
    ++ idx;
    return;
}
bool dfsearch(int u, int nowcol) {
    color[u] = nowcol;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int e = to[i];
        if (color[e] == 0) {
            if (!dfsearch(e, -nowcol)) {
                return false;
            }
        } else {
            if (color[e] == nowcol) {
                return false;
            }
        }
    }
    return true;
}

int main(void) {
    scanf("%d", &t);
    while (t --) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            head[i] = -1;
            color[i] = 0;
        }
        idx = 0;
        int inpu, inpv;
        for (int i = 1; i <= m; ++ i) {
            scanf("%d%d", &inpu, &inpv);
            add(inpu, inpv);
            add(inpv, inpu);
        }
        bool flag = true;
        for (int i = 1; i <= n && flag; ++ i) {
            if (color[i] == 0) {
                flag = dfsearch(i, 1);
            }
        }
        puts(flag ? "Y" : "N");
    }

    return 0;
}