旅行计划
测试数据来自 system/1959
描述
在有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