题目限制

1000 ms 128 M

题目描述

你和小伙伴正在玩赛车游戏，在一个方形区域内搭了很多方柱体作为桥墩，每个编号为1到N，每个桥墩有一定高度。现在你手中有一些轨道，由于轨道长度和数量限制，只能连接高度差不能超过d的桥墩。现在已知N个桥墩高度，求这个区域内最高的桥墩和最低的桥墩差距最大是多少？数据保证所有桥墩之间都是联通的。

输入格式

第一个一个数T，表示测试数据数量（T<=5,2<=N<=50,0<=d<=1000） 每组数据第一行两个数N和d

接下来一个N行N列的矩阵，第i行j列为Y表示i和j之间建了轨道，否则表示没有建，保证第i行j列和第j行i列值相同，并且第i行第i列值为N

输出格式

T行，每行一个答案，若最大值可能为正无穷，输出-1

数据范围

对于20%的数据，T<=3,N<=40 对于50%的数据，T<=3

对于100%的数据，T<=5,2<=N<=50,0<=d<=1000

输入样例

3

3 10

NYN

YNY

NYN

2 1

NN

NN

6 1000

NNYNNN

NNYNNN

YYNYNN

NNYNYY

NNNYNN

NNNYNN

输出样例

20

-1

3000

样例解释

第一个样例，1和2之间不能超过d，2和3之间不能超过d，那么最大就是1和2差恰好为d，2和3差 恰好为d

第二个样例，1和2之间没有限制，那么他们之间可能差为正无穷