시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 298 72 42 32.812%

문제

선영이는 새로운 퍼즐을 하나 만들었다. 퍼즐은 선영이가 만든 조각을 가지고 진행한다. 조각은 L모양이며, 정사각형 세 개를 붙여서 만든다. 모서리쪽에 있는 정사각형은 검정 색이고, 나머지는 흰 색이다. 아래 그림은 퍼즐에 사용하는 조각이다.

퍼즐의 목표는 위의 L조각을 이용해서 검정색과 흰색으로 이루어진 직사각형 패턴을 만드는 것이다. 조각은 회전시킬 수 있지만, 겹쳐서 놓을 수는 없다.

선영이는 멋진 패턴을 여러개 만들었다. 선영이가 만든 패턴이 만들 수 있는 패턴인지 아닌지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100을 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 패턴의 높이 n과 너비 m이 주어진다. (1 ≤ n, m ≤ 500) 다음 n개 줄에는 패턴이 주어진다. 'B'는 검정색, 'W'는 흰색, '.'은 빈 칸이다.

패턴에는 검정색이나 흰색 칸이 적어도 한 개 있다.

출력

각 테스트 케이스에 대해서, L조각을 가지고 입력으로 주어진 패턴을 만들 수 있으면 YES를, 만들 수 없으면 NO를 출력한다. 조각은 무한히 많다고 가정한다.

예제 입력 1

2
3 4
BWW.
WWBW
..WB
3 3
W..
BW.
WBW

예제 출력 1

YES
NO
W3sicHJvYmxlbV9pZCI6IjM2NTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJMXHVkMzdjXHVjOTkwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ1NThcdWIwOTggXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWQzN2NcdWM5OTBcdWM3NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlMCBcdWM4NzBcdWFjMDFcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gXHVjODcwXHVhYzAxXHVjNzQwIExcdWJhYThcdWM1OTFcdWM3NzRcdWJhNzAsIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWMxMzggXHVhYzFjXHViOTdjIFx1YmQ5OVx1YzVlY1x1YzExYyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YmFhOFx1YzExY1x1YjlhY1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YWM4MFx1YzgxNSBcdWMwYzlcdWM3NzRcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBcdWQ3NzAgXHVjMGM5XHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDM3Y1x1Yzk5MFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjODcwXHVhYzAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzN3B4OyB3aWR0aDoxMzJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQzN2NcdWM5OTBcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YzcwNFx1Yzc1OCBMXHVjODcwXHVhYzAxXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWFjODBcdWM4MTVcdWMwYzlcdWFjZmMgXHVkNzcwXHVjMGM5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMzI4XHVkMTM0XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWQ2OGNcdWM4MDRcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYywgXHVhY2I5XHVjY2QwXHVjMTFjIFx1YjE5M1x1Yzc0NCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYTRiXHVjOWM0IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWM1ZWNcdWI3ZWNcdWFjMWMgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1ZDMyOFx1ZDEzNFx1Yzc3NCBcdWI5Y2NcdWI0ZTQmbmJzcDtcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDMyOFx1ZDEzNFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzI4XHVkMTM0XHVjNzU4IFx1YjE5Mlx1Yzc3NCBuXHVhY2ZjIFx1YjEwOFx1YmU0NCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuLCBtICZsZTsgNTAwKSBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMzI4XHVkMTM0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTtCJiMzOTtcdWIyOTQgXHVhYzgwXHVjODE1XHVjMGM5LCAmIzM5O1cmIzM5O1x1YjI5NCBcdWQ3NzBcdWMwYzksICYjMzk7LiYjMzk7XHVjNzQwIFx1YmU0OCBcdWNlNzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDMyOFx1ZDEzNFx1YzVkMFx1YjI5NCBcdWFjODBcdWM4MTVcdWMwYzlcdWM3NzRcdWIwOTggXHVkNzcwXHVjMGM5IFx1Y2U3OFx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBMXHVjODcwXHVhYzAxXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDMyOFx1ZDEzNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBZRVNcdWI5N2MsIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0IE5PXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODcwXHVhYzAxXHVjNzQwIFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWI5Y2VcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaWVjZSBpdCB0b2dldGhlciIsImRlc2NyaXB0aW9uIjoiPHA+VG9tIGhhcyBkZXZlbG9wZWQgYSBzcGVjaWFsIGtpbmQgb2YgcHV6emxlOiBpdCBpbnZvbHZlcyBhIHdob2xlIGJ1bmNoIG9mIGlkZW50aWNhbCBwdXp6bGUgcGllY2VzLiBUaGUgcGllY2VzIGhhdmUgdGhlIHNoYXBlIG9mIHRocmVlIGFkam9pbnQgc3F1YXJlcyBpbiBhbiBMLXNoYXBlLiBUaGUgY29ybmVyIHNxdWFyZSBpcyBibGFjaywgdGhlIHR3byBhZGphY2VudCBzcXVhcmVzIGFyZSB3aGl0ZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9scC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzdweDsgd2lkdGg6MTMycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIHB1enpsZXIgaXMgZ2l2ZW4gYSBwYXR0ZXJuIG9mIGJsYWNrIGFuZCB3aGl0ZSBzcXVhcmVzIGluIGEgcmVjdGFuZ3VsYXIgZ3JpZC4gVGhlIGNoYWxsZW5nZSBpcyB0byBjcmVhdGUgdGhhdCBwYXR0ZXJuIHVzaW5nIHRoZXNlIHBpZWNlcy4gVGhlIHBpZWNlcyBjYW4gYmUgcm90YXRlZCwgYnV0IG11c3Qgbm90IG92ZXJsYXAuPFwvcD5cclxuXHJcbjxwPlRvbSBoYXMgYWxyZWFkeSBkZXNpZ25lZCBhIGZldyBuaWNlIHBhdHRlcm5zLCBidXQgaGUgbmVlZHMgdG8gXHVmYjAxbmQgb3V0IGlmIHRoZXkgY2FuIGJlIGNvbnN0cnVjdGVkIHdpdGggdGhlIHBpZWNlcyBhdCBhbGwuIFJhdGhlciB0aGFuIHRyeWluZyB0byB0ZXN0IHRoaXMgZm9yIGVhY2ggcGF0dGVybiBieSBoYW5kLCBoZSB3YW50cyB0byB3cml0ZSBhIGNvbXB1dGVyIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoaXMgZm9yIGhpbS4gQ2FuIHlvdSBoZWxwIGhpbT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBuIGFuZCBtICgxICZsZTsgbiwgbSAmbGU7IDUwMCk6IHRoZSBoZWlnaHQgYW5kIHdpZHRoIG9mIHRoZSBncmlkIGNvbnRhaW5pbmcgdGhlIHBhdHRlcm4sIHJlc3BlY3RpdmVseS48XC9saT5cclxuXHQ8bGk+biBsaW5lcywgZWFjaCBjb250YWluaW5nIG0gY2hhcmFjdGVycywgZGVub3RpbmcgdGhlIGdyaWQuIEVhY2ggY2hhcmFjdGVyIGlzICZsc3F1bztCJnJzcXVvOywgJmxzcXVvO1cmcnNxdW87LCBvciAmbHNxdW87LiZyc3F1bzssIGluZGljYXRpbmcgYSBibGFjaywgd2hpdGUgb3IgZW1wdHkgc3F1YXJlIHJlc3BlY3RpdmVseS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgZ3JpZCBjb250YWlucyBhdCBsZWFzdCBvbmUgYmxhY2sgb3Igd2hpdGUgc3F1YXJlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBlaXRoZXIgJmxkcXVvO1lFUyZyZHF1bzsgb3IgJmxkcXVvO05PJnJkcXVvOywgaW5kaWNhdGluZyB3aGV0aGVyIG9yIG5vdCBpdCBpcyBwb3NzaWJsZSB0byBjb25zdHJ1Y3QgdGhlIHBhdHRlcm4gd2l0aCB0aGUgcHV6emxlIHBpZWNlcy4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBpcyBhbiBpblx1ZmIwMW5pdGUgc3VwcGx5IG9mIHBpZWNlcy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==