#include <cstdio>
#include <vector>
#include <algorithm>
#define pb push_back
using std::vector;
using std::fill_n;
using ll = long long;

constexpr int N = 1005;
constexpr int M = 5005;

int n, m;
vector<int> t[N];
int c2[N][N], c3[N][N], c4[N][N], c5[N][N], ind[N][N], sp4[M][N];
ll c6[N][N], c7[N][N];

template <typename Int>
void clr(Int (&f)[N][N]) {
    for (int i = 1; i <= n; ++i) {
        fill_n(f[i] + 1, n, 0);
    }
}

inline int incl3(int u, int v, int i) {
    return c2[i][u] * c2[i][v];
}

inline int excl3_2(int u, int v, int i, int j) {
    return c3[u][v] - incl3(u, v, i) - incl3(v, u, j);
}

inline int excl3(int u, int v, int i) {
    return c3[u][v] - incl3(u, v, i);
}

inline int incl4(int u, int v, int i) {
    return c2[i][u] * excl3(i, v, u) + c2[i][v] * excl3(i, u, v);
}

inline int incl4_2(int u, int v, int i, int j) {
    return c2[i][j] * (c2[i][u] * c2[j][v] + c2[i][v] * c2[j][u]);
}

inline int excl4_2(int u, int v, int i, int j) {
    return c4[u][v] - incl4(u, v, i) - incl4(v, u, j) + incl4_2(u, v, i, j);
}

inline int excl4(int u, int v, int i) {
    return c4[u][v] - incl4(u, v, i);
}

inline int incl5(int u, int v, int i) {
    return c2[i][u] * excl4(i, v, u) + c2[i][v] * excl4(i, u, v)
        + excl3(i, u, v) * excl3(i, v, u) - sp4[ind[u][i]][v];
}

inline int incl5_2(int u, int v, int i, int j) {
    return excl3_2(i, j, u, v) * (c2[i][u] * c2[j][v] + c2[i][v] * c2[j][u])
        + c2[i][j] * (
            excl3_2(i, u, j, v) * c2[j][v] + excl3_2(i, v, j, u) * c2[j][u]
            + excl3_2(j, u, i, v) * c2[i][v] + excl3_2(j, v, i, u) * c2[i][u]
        );
}

inline int excl5_2(int u, int v, int i, int j) {
    return c5[u][v] - incl5(u, v, i) - incl5(v, u, j) + incl5_2(u, v, i, j);
}

void count3() {
    clr(c3);
    for (int i = 1; i <= n; ++i)
        for (int u : t[i])
            for (int v : t[i])
                if (u != v) {
                    ++c3[u][v];
                }
}

void count4() {
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            c4[i][j] = 0;
            for (int u : t[i])
                for (int v : t[j])
                    if (i != v && u != j && u != v) {
                        c4[i][j] += c2[u][v];
                    }
            c4[j][i] = c4[i][j];
        }
}

void count5() {
    count3();
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            c5[i][j] = 0;
            for (int u : t[i])
                for (int v : t[j])
                    if (i != v && u != j && u != v) {
                        c5[i][j] += excl3_2(u, v, i, j);
                    }
            c5[j][i] = c5[i][j];
        }
}

void count6() {
    count4();
    count3();
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            c6[i][j] = 0;
            for (int u : t[i])
                for (int v : t[j])
                    if (i != v && u != j && u != v) {
                        c6[i][j] += excl4_2(u, v, i, j);
                    }
            c6[j][i] = c6[i][j];
        }
}

void count7() {
    count5();
    count4();
    for (int i = 1; i <= m; ++i) {
        fill_n(sp4[i] + 1, n, 0);
    }
    for (int i = 1; i <= n; ++i)
        for (int u = i + 1; u <= n; ++u)
            if (c2[i][u])
                for (int j = 1; j <= n; ++j)
                    if (j != i && j != u && c2[j][i] && c2[j][u])
                        for (int v : t[j])
                            if (v != i && v != u) {
                                ++sp4[ind[i][u]][v];
                            }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            c7[i][j] = 0;
            for (int u : t[i])
                for (int v : t[j])
                    if (i != v && u != j && u != v) {
                        c7[i][j] += excl5_2(u, v, i, j);
                    }
            c7[j][i] = c7[i][j];
        }
}

template <typename Int>
void out(Int (&f)[N][N]) {
    static char s[N];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            s[j - 1] = "NY"[f[i][j] > 0];
        }
        s[n] = 0;
        puts(s);
    }
}

int main() {
    int q, u, v, k;
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= n; ++i) {
            t[i].clear();
        }
        clr(c2);
        clr(ind);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            t[u].pb(v);
            t[v].pb(u);
            ++c2[u][v];
            ++c2[v][u];
            ind[u][v] = i;
            ind[v][u] = i;
        }
        if (k == 2) {
            out(c2);
        }
        if (k == 3) {
            count3();
            out(c3);
        }
        if (k == 4) {
            count4();
            out(c4);
        }
        if (k == 5) {
            count5();
            out(c5);
        }
        if (k == 6) {
            count6();
            out(c6);
        }
        if (k == 7) {
            count7();
            out(c7);
        }
    }
}