#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int T, n, m, k, a[310], b[310], blg[310], f[310];
bool flag, used[310];

int gf(int f[], int x) { return f[x] == x ? x : f[x] = gf(f, f[x]); }

bool dfs(int id) {
    int g[310];
    for (int i = 1; i <= n; ++i) g[i] = i;
    for (int i = 1; i <= m; ++i)
        if (blg[i] == id) {
            int fx = gf(g, a[i]), fy = gf(g, b[i]);
            g[fx] = fy;
        }
    for (int i = 1; i <= m; ++i) {
        int fx = gf(g, a[i]), fy = gf(g, b[i]);
        if (fx != fy && !used[i]) {
            used[i] = 1;
            if (!blg[i]) {
                blg[i] = id;
                return 1;
            }
            int tmp = blg[i];
            blg[i] = id;
            if (dfs(tmp))
                return 1;
            blg[i] = tmp;
        }
    }
    return 0;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= m; ++i) scanf("%d%d", &a[i], &b[i]);
        if ((n - 1) * k > m) {
            puts("No");
            continue;
        }
        
        flag = 1;
        memset(blg, 0, sizeof(blg));
        for (int id = 1; flag && id <= k; ++id) {
            memset(used, 0, sizeof(used));
            for (int i = 1; i <= n; ++i) f[i] = i;
            for (int i = 1; i <= m; ++i)
                if (!blg[i]) {
                    int fx = gf(f, a[i]), fy = gf(f, b[i]);
                    if (fx != fy) {
                        f[fx] = fy;
                        blg[i] = id;
                    }
                }
            for (int i = 1; i <= m; ++i) {
                int fx = gf(f, a[i]), fy = gf(f, b[i]);
                if (fx != fy) {
                    memset(used, 0, sizeof(used));
                    used[i] = 1;
                    int tmp = blg[i];
                    blg[i] = id;
                    if (dfs(tmp))
                        f[fx] = fy; else
                        blg[i] = tmp;
                }
            }
            for (int i = 2; i <= n; ++i)
                if (gf(f, 1) != gf(f, i)) {
                    flag = 0;
                    break;
                }
        }
        
        puts(flag ? "Yes" : "No");
    }
    return 0;
}