FLING1 - FLING1


Fling! is a popular puzzle game created by the well-known developers at Candy Cane LLC.

The premise of the game is simple. You are given a certain number of balls on the screen to start. The goal is to fling one into another in order to knock the other off the screen. The puzzle is considered solved if you can do so while leaving only one ball remaining on the screen. Some might read this and think that it might not be too difficult, but the game gets challenging quickly. The problem is that you cannot fling two balls that are adjacent (i.e. next to each other.)

The first ball you choose can fling the 2nd ball if and only if:

  1. The two balls exist in same row or same column.
  2. The two balls are not adjacent.
  3. There is no other ball in between the two balls.

If there exist a 3rd ball after the 2nd ball in the same line of action, the 2nd ball takes the position just before the third ball, pushes the 3rd ball and the 3rd ball gets flinged. (This continues until a ball gets knocked off the screen. Note that 2nd ball and 3rd ball can be adjacent).

Given a Fling! puzzle, just print "Yes" if it is a valid puzzle (solvable) or "No" otherwise.

For better understanding of gameplay you may have a look at this video. (optional)

Input

The first line of the input consists of an integer t, the number of test cases. For each test case, the first line consists of two integers m and n, the number of rows and columns of the puzzle. Then follows the description of the board. A[i][j] is '.' if the cell is empty or 'B' if the cell has a ball.

Output

For each test case print "Yes" if the puzzle is valid or "No" otherwise. (case-sensitive).

Constraints

1 <= t <= 100

1 <= m, n <= 10

You can assume that the number of balls in the board is approximately equal to (m x n) / 10.

Sample

Input:
4
5 5
.....
.....
..B..
.....
.B..B
5 4
....
B...
B...
....
B...
3 4
BB..
....
.B..
1 1
B

Output:
Yes
Yes
No
Yes

hide comments
Alex Anderson: 2014-04-17 09:41:01

What does "approximately equal to (m x n)/10" mean? Will it always be less? Sometimes more? I think it might be possible (for me) if the number of balls is always less than 10 or 11.

:D: 2014-04-17 09:41:01

For now I don't know how to solve it efficiently with those constrains :)

Francky: 2014-12-12 11:11:34

This could make a good problem with higher constraints. ...

:D: 2014-04-17 09:41:01

Just to be sure. Number of ball is only limited by board dimensions, right? And test cases are exploiting that?

Reply: You can assume that the number of balls in the board is approximately equal to ( m x n ) /10

Last edit: 2013-03-07 14:32:55

Added by:cegprakash
Date:2013-02-24
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU