Sample Input

4

6

6

0 3

1 5

3 2

2 5

0 4

1 0

7

12

6 5

0 3

2 6

3 5

5 0

0 4

4 5

6 3

1 4

1 2

3 4

2 3

7

8

6 5

0 3

2 6

3 5

1 4

1 2

3 4

2 3

6

9

0 1

1 2

2 3

5 2

5 3

3 4

2 4

1 4

4 5

Sample Output

Y

N

Y

N

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxn = ;

const int maxm = ;

const int INF=0x7f7f7f7f;

int v[maxm], nxt[maxm], last[maxm];

int vis[maxn], d[maxn];

vector<int> vc[maxn];

int sz = ;

int n, m;

void DFS(int k, int p)

{

    vc[p].push_back(k);

    vis[k] = ;

    for (int i = last[k]; i; i = nxt[i])

        if (!vis[v[i]]) DFS(v[i], p);

}

void init()

{

    sz = ;

    for (int i = ; i < maxn; i++) vc[i].clear();

    memset(last, , sizeof(last));

    memset(vis, , sizeof(vis));

    memset(d, , sizeof(d));

}

void build(int x, int y)

{

    sz++;

    v[sz] = y, nxt[sz] = last[x], last[x] = sz;

}

bool ok(int k)

{

    for (int i = last[k]; i; i = nxt[i])

        if (d[k] == d[v[i]]) return false;

    return true;

}

bool check(int p, int k)

{

    if (k == vc[p].size()) return true;

    int x = vc[p][k];

    for (int i = ; i <= ; i++)

    {

        d[x] = i;

        if (!ok(x)) continue;

        if (check(p, k+)) return true;

    }

    d[x] = ;

    return false;

}

int main()

{

    int t;

    scanf("%d", &t);

    for (int ca = ; ca <= t; ca++)

    {

        init();

        scanf("%d%d", &n, &m);

        for (int i = ; i <= m; i++)

        {

            int x, y;

            scanf("%d%d", &x, &y);

            build(x, y), build(y, x);

        }

        int cnt = ;

        for (int i = ; i < n; i++)

            if (!vis[i])

            {

                ++cnt;

                DFS(i, cnt);

            }

        int flag = true;

        for (int i = ; i <= cnt; i++)

            if (!check(i, )) { flag = false; break; }

        printf("%c\n", flag ? 'Y':'N');

    }

}