玩游戏2

游戏是在一个无环的无向图中进行的，每个点上面有一些金币。

每次小 K 可以对一个金币数 $\ge 2$ 的点进行操作：拿走一个金币，并将另一个金币放到它相邻的点上。游戏中有一个点叫做 Target Point，如果在游戏的过程中 Target Point 上有金币的话，小 K 就赢了。

巧合的是，这个游戏是小 Z 开发的。在得知小 K 在玩这个游戏之后，为了报上次的一箭之仇，他决定设计金币的分布让小 K 必败。

而小 Z 深知小 K 光环的威力：如果放置的金币太少，小 K 会马上发现这个游戏是不可能赢的。于是他求助于你，他最多能放多少个金币呢？

输入格式

本题有多组数据。

每组数据的第一行为两个整数 $N, M$，表示共有 $N$ 个节点，而 $M$ 为 Target Point。

接下来 $N$ 行，每行为一个长度为 $N$ 的字符串，如果第 $i$ 个字符串的第 $j$ 个字符是 Y，则代表 $i$ 与 $j$ 之间有边。

输出格式

对每组数据输出一行，为最多能放的金币数；如果答案超过了 $2\times 10^9$ 则输出 $-1$。

样例输入

3 2
NYN
YNY
NYN
1 1
N

样例输出

2
0

数据范围

• $1\le M\le N\le 60$。

来源与许可

本题题面与测试数据整理自 BZOJ 2681。

样例 1

输入

3 2
NYN
YNY
NYN
1 1
N

输出

2
0