#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 1010
#define maxm 5010
#define pb push_back
using namespace std;

int T, n, m, K;

int u[maxm], v[maxm];

struct Edge{
    int to, next;
}e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v){
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++; 
}

int g[maxn][maxn];

bool ans[maxn][maxn];
void put(){
    for(int i = 1; i <= n; ++i, putchar('\n'))
        for(int j = 1; j <= n; ++j){
            if(ans[i][j]) putchar('Y');
            else putchar('N');  
            ans[i][j] = 0;
        }
}

void solve_2(){
    for(int i = 1; i <= n; ++i)
        for(int j = head[i]; ~j; j = e[j].next) ans[i][e[j].to] = 1;
}

int a[maxn], c2;
void solve_3(){
    for(int i = 1; i <= n; ++i){
        int u = i; c2 = 0;
        for(int j = head[u]; ~j; j = e[j].next){
            int v = e[j].to; a[++c2] = v;
        }
        for(int j = 1; j <= c2; ++j)
            for(int k = 1; k < j; ++k)
                ans[a[j]][a[k]] = ans[a[k]][a[j]] = 1;
    }
}               

void solve_4(){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < i; ++j){
            bool F = 0;
            for(int l = head[i]; ~l && !F; l = e[l].next){
                int v1 = e[l].to; if(v1 == j) continue;
                for(int r = head[j]; ~r; r = e[r].next){
                    int v2 = e[r].to; if(v2 == i || v2 == v1) continue;
                    if(g[v1][v2]){F = 1; break;}
                }
            }
            ans[i][j] = ans[j][i] = F;
        }
}

int cnt[maxn];
void solve_5(){
    for(int p = 1; p <= n; ++p)
        for(int q = 1; q < p; ++q){
            int sum = 0; 
            for(int i = head[p]; ~i; i = e[i].next){
                int u = e[i].to; if(u == q || !g[u][q]) continue;
                cnt[u] = 1; ++sum;
            }
            for(int l = head[p]; ~l; l = e[l].next){
                int x = e[l].to; if(x == q) continue;
                for(int r = head[q]; ~r; r = e[r].next){
                    int y = e[r].to; if(y == p || y == x) continue;
                    ans[y][x] = (ans[x][y] |= sum - cnt[x] - cnt[y] > 0);
                }
            }
            for(int i = head[p]; ~i; i = e[i].next){
                int u = e[i].to; if(u == q) continue;
                cnt[u] = 0;
            }
        }
}

void solve_6(){
    for(int p = 1; p <= n; ++p)
        for(int q = 1; q < p; ++q){
            int sum = 0; 
            for(int l = head[p]; ~l; l = e[l].next){
                int u = e[l].to; if(u == q) continue;
                for(int r = head[q]; ~r; r = e[r].next){
                    int v = e[r].to; if(v == p || u == v || !g[u][v]) continue;
                    ++cnt[u]; ++cnt[v]; ++sum;
                }
            }
            for(int l = head[p]; ~l; l = e[l].next){
                int x = e[l].to; if(x == q) continue;
                for(int r = head[q]; ~r; r = e[r].next){
                    int y = e[r].to; if(y == p || x == y) continue;
                    ans[y][x] = (ans[x][y] |= sum - cnt[x] - cnt[y] + g[x][y] > 0);
                }
            }
            for(int l = head[p]; ~l; l = e[l].next){
                int u = e[l].to; if(u == q) continue;
                for(int r = head[q]; ~r; r = e[r].next){
                    int v = e[r].to; if(v == p || u == v || !g[u][v]) continue;
                    cnt[u] = cnt[v] = 0;
                }
            }
        }
}

vector<int> b[maxn][maxn];
int cnt1[maxn][maxn], cnt2[maxn][maxn], I;
int vis1[maxn][maxn], vis2[maxn][maxn];

int c[maxm], c3;

void solve_7(){
    memset(vis1, 0, sizeof vis1); memset(vis2, 0, sizeof vis2); I = 0; 
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) b[i][j].clear();
    for(int i = 1; i <= n; ++i){
        int u = i; c2 = 0;
        for(int j = head[u]; ~j; j = e[j].next){
            int v = e[j].to;
            a[++c2] = v;
        }
        for(int j = 1; j <= c2; ++j)
            for(int k = 1; k < j; ++k){
                b[a[j]][a[k]].pb(i);
                b[a[k]][a[j]].pb(i);
            }
    }
    for(int u = 1; u <= n; ++u)
        for(int v = 1; v < u; ++v){
            int sum = 0; ++I; c3 = 0;
            for(int i = head[u]; ~i; i = e[i].next){
                int p = e[i].to; if(p == v) continue;
                for(int j = head[v]; ~j; j = e[j].next){
                    int q = e[j].to; if(q == u || p == q) continue;
                    for(int k = 0, _s = b[p][q].size(); k < _s; ++k){
                        int z = b[p][q][k]; if(z == u || z == v) continue;
                        
                        c[++c3] = z;
                        
                        if(vis1[p][q] == I) ++cnt1[p][q];
                        else vis1[p][q] = I, cnt1[p][q] = 1;
                        
                        if(vis2[p][z] == I) ++cnt2[p][z];
                        else vis2[p][z] = I, cnt2[p][z] = 1;
                        
                        if(vis2[q][z] == I) ++cnt2[q][z];
                        else vis2[q][z] = I, cnt2[q][z] = 1;
                        
                        ++cnt[q]; ++cnt[p]; ++cnt[z]; ++sum;
                    }
                }
            }   
            for(int i = head[u]; ~i; i = e[i].next){
                int p = e[i].to; if(p == v) continue;
                for(int j = head[v]; ~j; j = e[j].next){
                    int q = e[j].to; if(q == u || p == q) continue;
                    if(vis1[p][q] != I) cnt1[p][q] = 0;
                    if(vis2[p][q] != I) cnt2[p][q] = 0;
                    if(vis2[q][p] != I) cnt2[q][p] = 0;
                    ans[p][q] |= (sum - cnt[p] - cnt[q] + cnt1[p][q] + cnt2[p][q] + cnt2[q][p] > 0);
                    ans[q][p] = ans[p][q];
                }
            }
            for(int i = 1; i <= c3; ++i) cnt[c[i]] = 0;
            for(int i = head[u]; ~i; i = e[i].next) cnt[e[i].to] = 0;
            for(int i = head[v]; ~i; i = e[i].next) cnt[e[i].to] = 0;
        }
}

void work(){
    memset(head, -1, sizeof head); c1 = 0;
    scanf("%d%d%d", &n, &m, &K);
    for(int i = 1; i <= m; ++i){
        int x, y; scanf("%d%d", &x, &y);
        add_edge(x, y); add_edge(y, x);
        g[x][y] = g[y][x] = 1;
        u[i] = x; v[i] = y;
    }
    switch(K){
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;
        case 4 : solve_4(); break;
        case 5 : solve_5(); break;
        case 6 : solve_6(); break;
        case 7 : solve_7(); break;
    } put();
    for(int i = 1; i <= m; ++i) g[u[i]][v[i]] = g[v[i]][u[i]] = 0;
}

int main(){
    scanf("%d", &T);
    while(T--) work();
}

..........................
给跪了
k=2 O(n^2)
k=3 O(nm)
k=4 O(m^2)
然后k=5利用k=4的结果 可以做到O(m^2+n^3/32)
然后k=6利用k=4的结果 可以做到O(m^2+n^2m/32)
然后k=7利用k=5的结果 可以做到O(m^2+nm^2/32)
好像k=7的还是错的.... 不过能过数据
bitset真是个好东西...
直接压位+利用好k=4/5的结果
搞搞可以过...
这不是正解.
k=5/6/7都是压位做的....
这个算法被出题人喷死了233

这题有点厉害，折腾出来了55分算法，感觉75分也近在咫尺了。
恩，感觉100分我也知道怎么写了，不过有点复杂。

这题居然是动态规划，给跪了。