题目描述

图片:hina正在玩的RPG

​ hina现在正在玩一款RPG的游戏，游戏里有一个迷宫。hina想从迷宫的左上角到右下角,但是miyane不想让hina走出迷宫,于是她设置了一些墙壁来阻挡hina,你能帮miyane设置墙壁来阻挡hina走出迷宫吗？或者告诉miyane无法阻挡hina走出迷宫。

​ 为了简便起见，我们可以把迷宫看做一个$n\ imes m$的字符矩阵类似下图是一个$3 \ imes 4$的字符矩阵:

​ $S...$

​ $.$#$..$

​ $...E$

​ 其中$S$代表hina的起始位置,hina的起始位置一定在左上角,$E$代表迷宫的出口,$E$一定在右下角,#代表墙壁, $.$ 代表可以经过的地方。说明：S的坐标是(1,1)，E的坐标是(n,m)。

​ 我们的hina因为等级比较高可以往周围一圈8个方向行走也就是说它可以上下左右也可以斜上斜下走。

​ 对于上面给定的图可以看出hina一定是可以走到终点的。

​ miyane只能在 . 上设置墙壁，不能在S或E或#的位置设置墙壁。

输入格式

第一行一个正整数 $T$ 代表输入的数据组数, $1\\leq T\\leq 100$

每组数据首先包含三个正整数$n,m,k, 2\\leq n,m \\leq50, 3\\leq k\\leq10$代表迷宫的大小和miyane能够最多设置的墙壁数量

然后一个$n\ imes m$的字符矩阵代表迷宫

输出格式

对于每组测试数据,如果miyane能够通过设置最多$k$次墙壁来阻挡hina走出迷宫的话,输出YES, 然后输出一个正整数$x$代表miyane需要设置的墙壁的数量$0\\leq x\\leq k$

接下来输出$x$行,每行两个正整数$x_i,y_i, 1\\leq x_i\\leq n, 1\\leq y_i\\leq m$代表放置墙壁的坐标,墙壁只能放在$.$上

如果有多种答案符合要求，输出任意一种

如果miyane不能通过放置最多$k$次的墙壁来阻挡hina,输出一行NO

样例

1 
5 5 5 
S.... 
..... 
..... 
..... 
....E

YES 
5 
3 1 
3 2 
3 3 
3 4 
3 5

提示

样例放置墙壁后如下:

$S....$

$.....$

\#\#\#\#\#​

$.....$

$....E$

可以保证hina无法从起点到终点