E. Dots and Boxes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
ConsW is an expert in Dots and Boxes. He gathered Alice and Bob for a match.

Alice and Bob are playing a classic game known as "Dots and Boxes".

The game is played on a rectangular grid of size $$$n \times m$$$. The game proceeds as follows:

  • Alice and Bob take turns adding a single horizontal or vertical edge between two adjacent unconnected cells. Alice goes first.
  • If placing an edge completes a $$$1 \times 1$$$ cell (i.e., the cell is surrounded by 4 edges), the current player scores $$$1$$$ point and must take another turn immediately. The player continues to take turns as long as they complete a cell.
  • If the placed edge does not complete any cell, the turn ends, and the other player begins their turn.
  • The game ends when all edges have been drawn and all cells are completed. The player with the higher score wins.

Alice and Bob have paused the game in a specific state. Currently, every single cell $$$(i, j)$$$ in the grid is surrounded by exactly 2 drawn edges and 2 empty edges. Since no cells are fully completed yet, the current score is $$$0-0$$$.

Given this board state, Alice takes the next move. Determine whether Alice has a winning strategy regardless of how Bob plays. Alice wins if Alice's score is strictly greater than Bob's score at the end of the game.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n \cdot m \le 4 \cdot 10^5$$$) — the number of rows and columns of the grid.

The next $$$n \cdot m$$$ lines of each test case describe the state of each cell. The lines are ordered cell by cell: row $$$1$$$ from left to right, then row $$$2$$$, and so on, up to row $$$n$$$.

Each line contains two characters $$$c_1, c_2$$$ ($$$c_1, c_2 \in $$$ { 'U', 'D', 'L', 'R' }), representing the positions of the two edges already drawn for that cell:

  • 'U': The upper edge is drawn.
  • 'D': The lower edge is drawn.
  • 'L': The left edge is drawn.
  • 'R': The right edge is drawn.

It is guaranteed that the input describes a valid grid topology (e.g., if cell $$$(1,1)$$$ has a right edge 'R', then cell $$$(1,2)$$$ must have a left edge 'L').

Additional constraints on the input: the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each case, print a single line containing "YES" if Alice has a winning strategy, and "NO" otherwise. The output is case-insensitive (e.g., "Yes", "yes", "yEs" are all accepted).

Example
Input
2
2 2
U L
U R
D L
D R
3 3
U L
U D
U R
L D
U D
D R
L U
U D
U R
Output
NO
YES
Note

In the first example, the board is a $$$2 \times 2$$$ grid. The outer boundary edges are drawn, but the internal cross is missing. Regardless of which internal edge Alice draws, she will not complete a square on that turn, and Bob will be able to take all $$$4$$$ squares in the subsequent turns.

The illustration of the first sample.