Z-Game on grid
题号:NC239809
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Alice and Bob are playing a game on an grid where each cell has either 'A', 'B' or '.' written on it. They take turns moving a chess piece on the grid and Alice moves first.

Initially the piece is on cell (1,1). In each player's turn, he or she can move the piece one cell right or one cell down. That is, if the piece is on cell (x,y) before the turn, the player can move it to or , as long as it doesn't go beyond the grid.

At any time, if the piece is on a cell with 'A', Alice wins and the game ends. If the piece is on a cell with 'B', Bob wins and the game ends. If the piece reaches cell (n,m) without the game ending, then it is a draw.

Since Alice cannot decide what acts Bob will take, she would like to know if she can be in control of the situation. Given the grid they're playing on, can you tell her if she can always find a way to win, draw or lose the game no matter what acts Bob takes?

输入描述:

In the first line an integer , representing the number of test cases.

For each test case, the first line contains two integers , representing the grid's size.

Each of the next N lines for the case contains M characters (either 'A', 'B' or '.'), describing the grid.

输出描述:

For each test case, output three words 'yes' or 'no' in one line, representing if Alice can find a way to win, draw or lose the game respectively (without quotes).
示例1

输入

复制
2
3 3
..B
..B
BB.
1 3
...

输出

复制
no no yes
no yes no