310803: CF1890B. Qingshan Loves Strings

B. Qingshan Loves Stringstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Qingshan has a string $s$, while Daniel has a string $t$. Both strings only contain $\texttt{0}$ and $\texttt{1}$.

A string $a$ of length $k$ is good if and only if

• $a_i \ne a_{i+1}$ for all $i=1,2,\ldots,k-1$.

For example, $\texttt{1}$, $\texttt{101}$, $\texttt{0101}$ are good, while $\texttt{11}$, $\texttt{1001}$, $\texttt{001100}$ are not good.

Qingshan wants to make $s$ good. To do this, she can do the following operation any number of times (possibly, zero):

• insert $t$ to any position of $s$ (getting a new $s$).

Please tell Qingshan if it is possible to make $s$ good.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1\le T\le 2000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 50$) — the length of the strings $s$ and $t$, respectively.

The second line of each test case contains a string $s$ of length $n$.

The third line of each test case contains a string $t$ of length $m$.

It is guaranteed that $s$ and $t$ only contain $\texttt{0}$ and $\texttt{1}$.

Output

For each test case, print "YES" (without quotes), if it is possible to make $s$ good, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).

ExampleInput

5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10

Output

Yes
Yes
No
No
No

Note

In the first test case, $s$ is good initially, so you can get a good $s$ by doing zero operations.

In the second test case, you can do the following two operations (the inserted string $t$ is underlined):

1. $\texttt{1}\underline{\texttt{010}}\texttt{11}$
2. $\texttt{10101}\underline{\texttt{010}}\texttt{1}$

and get $s = \texttt{101010101}$, which is good.

In the third test case, there is no way to make $s$ good after any number of operations.

**题目大意：**
青杉有一个只包含 '0' 和 '1' 的字符串 s，而丹尼尔有一个字符串 t，也只包含 '0' 和 '1'。一个长度为 k 的字符串 a 是好的，当且仅当对于所有 i=1,2,…,k-1，都有 a_i ≠ a_{i+1}。青杉可以通过将 t 插入到 s 的任意位置（得到新的 s）来使 s 变好。需要判断是否可能使 s 变好。

**输入数据格式：**
第一行包含一个整数 T（1≤T≤2000），表示测试用例的数量。接下来是 T 个测试用例的描述。
每个测试用例包含三行：
- 第一行包含两个整数 n 和 m（1≤n,m≤50），分别表示字符串 s 和 t 的长度。
- 第二行包含一个长度为 n 的字符串 s。
- 第三行包含一个长度为 m 的字符串 t。

**输出数据格式：**
对于每个测试用例，如果可以使 s 变好，则输出 "YES"，否则输出 "NO"。输出大小写不限。

**示例：**
```
输入：
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10

输出：
Yes
Yes
No
No
No
```

**注意：**
- 在第一个测试用例中，s 初始就是好的，所以可以通过零次操作得到好的 s。
- 在第二个测试用例中，可以通过两次操作得到好的 s。
- 在第三个测试用例中，任何数量的操作都无法使 s 变好。**题目大意：** 青杉有一个只包含 '0' 和 '1' 的字符串 s，而丹尼尔有一个字符串 t，也只包含 '0' 和 '1'。一个长度为 k 的字符串 a 是好的，当且仅当对于所有 i=1,2,…,k-1，都有 a_i ≠ a_{i+1}。青杉可以通过将 t 插入到 s 的任意位置（得到新的 s）来使 s 变好。需要判断是否可能使 s 变好。 **输入数据格式：** 第一行包含一个整数 T（1≤T≤2000），表示测试用例的数量。接下来是 T 个测试用例的描述。 每个测试用例包含三行： - 第一行包含两个整数 n 和 m（1≤n,m≤50），分别表示字符串 s 和 t 的长度。 - 第二行包含一个长度为 n 的字符串 s。 - 第三行包含一个长度为 m 的字符串 t。 **输出数据格式：** 对于每个测试用例，如果可以使 s 变好，则输出 "YES"，否则输出 "NO"。输出大小写不限。 **示例：** ``` 输入： 5 1 1 1 0 3 3 111 010 3 2 111 00 6 7 101100 1010101 10 2 1001001000 10 输出： Yes Yes No No No ``` **注意：** - 在第一个测试用例中，s 初始就是好的，所以可以通过零次操作得到好的 s。 - 在第二个测试用例中，可以通过两次操作得到好的 s。 - 在第三个测试用例中，任何数量的操作都无法使 s 变好。