描述

在有N座城市的国度，Alice希望可以开始一场充满传奇的旅行。

TA希望可以从一个城市出发开始旅行，每次前往一个相邻的城市，途中不重复得经过恰好K座城市，最后抵达另外一个城市并结束旅行。
需要注意的是，起点与终点也被考虑为经过的城市，也就是说包括起点和终点在内经过的所有城市都是不能重复的。

现在，Alice希望知道哪些城市对<u,v>可以作为合法的旅行起点与终点。

格式

输入格式

本题每一个测试点有多组测试数据。第一行给定正整数T，表示数据组数。

之后，对于每一组数据来说，第一行给定三个整数N，M和K，表示城市个数，城市之间的相邻关系个数，还有旅途应该经过的城市个数。

之后M行，每一行给定两个整数u和v，表示标号为u的城市与标号为v的城市之间是相邻的，即可以从其中一个城市出发前往另外一个。

输出格式

对于每一组数据，输出N行，每行N个字符。

其中第i行第j个字符，或者为“Y”或者为“N”，分别表示是否存在从城市i出发到城市j结束的合法旅行方案。

样例1

样例输入1

1
5 6 4
1 2
2 3
3 5
1 4
4 5
2 5

样例输出1

NYYYY
YNNYY
YNNYN
YYYNY
YYNYN

限制

对于5%的数据，K<=2。
对于15%的数据，K<=3。
对于35%的数据，K<=4。
对于55%的数据，K<=5。
对于75%的数据，K<=6。
对于100%的数据，N<=1000，M<=5000，2<=K<=7且\(T\times \lfloor K/2\rfloor^{\lfloor K/2\rfloor} \le 60\)。

来源

SDOI 2015 round2 day1