C - ★★生命的游戏★★

时间限制： 1000ms

空间限制： 256MB

题目描述

生命游戏(Conway′s  Game  of  LifeConway’s )是英国数学家约翰·何顿·康威在 1970 年发明的一款“零玩家游戏”。
生命游戏的“棋盘”是一个$n×n$ 的网格，每个网格代表一个“细胞”，每个细胞有两种状态：“生”或“死”。生命游戏每隔一段时间进行一次演变，称为一个“回合”。
在生命游戏中，每个细胞在一个新回合的生与死只取决于它在上一个回合时周围$8$个细胞的存活状态，具体的规则如下：

. 如果一个死亡的的细胞周围恰好有 $3$ 个活的细胞，那么下一个回合时，这个细胞的状态将转为“生”

. 如果一个存活的的细胞周围活细胞的数量大于 $3$ 或小于 $2$，那么下一个回合时，这个细胞的状态将转为“死”

. 其他情况下，细胞的存活状态不变

特别地，我们规定第 $i$ 行第 $j$ 列的细胞为 $(i,j)$，且在“棋盘”边缘的细胞在位置上与另一侧循环相连。例如细胞 $(n,n)$ 的右侧是细胞 $(n,1)$，下方是细胞 $(1,n)$。
$Cindy$ 特别喜欢生命游戏，她常常能够在看似毫无规律的生命游戏中发现许多有趣的现象。例如对于某些初始状态，会在若干回合的演变之后再次回到最初的状态，即所有对应位置的细胞状态完全相同，我们便认为该初始状态存在周期。
例如，图 $C−1$ 在进行一次演变之后会变成图 $C−2$，再进行一次演变后又会重新变为 $C−1$，其周期为 $2$。(其中 ★ 代表“生”)

对于一个给定的初始状态，$Cindy$ 想知道在 $k$ 回合之内(包括第 $k$ 回合)该状态是否存在周期。

输入描述:

第一行一个整数 $T (1 \leq T \leq 100)$，表示测试用例的数量。
对于每组测试用例，第一行两个整数 $n,k(1 \leq n,k \leq 100)$，分别表示棋盘的大小和回合次数；
接下来 $n$ 行，一个 $n \times n$  的 $01$ 矩阵，表示初始状态。其中 $1$ 表示存活，$0$表示死亡。
对于全部测试用例，保证 $\sum n$, $\sum k \leq 100$ 。

输出描述:

对于每组测试用例，输出一行一个字符串，如果存在周期，先在第一行输出$YES$，然后在第二行输出第一次出现周期的回合数；如果不存在周期，直接输出一行$NO$。

输入

2
5 2
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0
5 50
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1

输出

YES
2
NO

说明

在第一组测试用例中，第一次出现周期的回合数为
$2$。在第二组测试用例中，在 $50$ 回合内初始状态不会出现周期。