
ZOJ Problem Set  4127
BaoBao has just found a grid with $n$ rows and $m$ columns in his left pocket, where the cell in the $j$th column of the $i$th row (indicated by $(i, j)$) contains an arrow (pointing either upwards, downwards, leftwards or rightwards) and an integer $a_{i, j}$. BaoBao decides to play a game with the grid. He will first select a cell as the initial cell and tick it. After ticking a cell (let's say BaoBao has just ticked cell $(i, j)$), BaoBao will go on ticking another cell according to the arrow and the integer in cell $(i, j)$.
If the cell BaoBao decides to tick does not exist, or if the cell is already ticked, the game ends. BaoBao is wondering if he can select a proper initial cell, so that he can tick every cell in the grid exactly once before the game ends. Please help him find the answer. InputThere are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($1 \le n \times m \le 10^5$), indicating the number of rows and columns of the grid. For the following $n$ lines, the $i$th line contains a string $s_i$ consisting of lowercased English letters ($s_i = m$, $s_{i, j} \in \{\text{'u' (ascii: 117)}, \text{'d' (ascii: 100)}, \text{'l' (ascii: 108)}, \text{'r' (ascii: 114)}\}$), where $s_{i, j}$ indicates the direction of arrow in cell $(i, j)$.
For the following $n$ lines, the $i$th line contains $m$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ ($1 \le a_{i, j} \le \max(n, m)$), where $a_{i, j}$ indicates the integer in cell $(i, j)$. It's guaranteed that the sum of $n \times m$ of all test cases does not exceed $10^6$. OutputFor each test case output one line. If BaoBao can find a proper initial cell, print "Yes" (without quotes), otherwise print "No" (without quotes). Sample Input2 2 3 rdd url 2 1 1 1 1 2 2 2 rr rr 1 1 1 1 Sample OutputYes No HintFor the first sample test case, BaoBao can select cell (1, 2) as the initial cell, so that he can tick all the cells exactly once in the following order: (1, 2), (2, 2), (2, 3), (2, 1), (1, 1), (1, 3). For the second sample test case, BaoBao can only tick at most 2 cells no matter which cell is selected as the initial cell. Author: WENG, Caizhi Source: The 2019 ICPC China Shaanxi Provincial Programming Contest 