题目描述

学校新建了一批宿舍，值日生小A要把所有的空房间都打扫一遍。这些宿舍的布局很奇怪，整个建筑物里所有的房间组成一个N * M的矩阵，每个房间的东南西北四面墙上都有一个门通向隔壁房间。另外有些房间是堆放杂物的，无需打扫。小A想设计若干条打扫路线，使得恰好进出每个需打扫的房间各一次，而且进出每个房间不能通过同一个门。要求每条路线都是一个闭合的环线，并且每条路线经过的房间数大于2。

如下面两图所示均为满足要求的打扫方案（灰色格子为放杂物的房间）：

小A发现对于某些房间布局是不存在这样的满足要求的方案的。他请你写一个程序计算一下，对于一种给定的房间布局，满足要求的方案是否存在。

输入格式

输入文件的第一行是一个整数T (1 ≤ T ≤ 10)，表示该文件中一共有T组数据。接下来依次是T组数据的信息。每组数据的第一行包含两个整数N和M，接下来的N行，每行包含M个字符，表示一个房间布局。字符'.'表示该房间需要打扫，'#'表示该房间是堆放杂物的，无需打扫。

输出格式

共输出T行，对每组数据输出一行，为"YES"或"NO"，表示打扫方案存在与否。

4
3 4
##..
....
....
3 4
##..
....
#...
3 4
##..
#...
#...
3 4
####
#..#
####

YES
NO
YES
NO

提示

对50%的数据，3 ≤ N,M ≤ 12

对100%的数据，3 ≤ N,M ≤ 30

每个测试点时限1秒