题目描述

青山有一个字符串 $s$，而 Daniel 有一个字符串 $t$。两个字符串都只包含 $\texttt{0}$ 和 $\texttt{1}$。

一个长度为 $k$ 的字符串 $a$ 是“好”的，当且仅当：

• 对于所有 $i=1,2,\ldots,k-1$，都有 $a_i \ne a_{i+1}$。

例如，$\texttt{1}$、$\texttt{101}$、$\texttt{0101}$ 是“好”的，而 $\texttt{11}$、$\texttt{1001}$、$\texttt{001100}$ 不是“好”的。

青山想让 $s$ 变成“好”的。为此，她可以进行如下操作任意次（也可以不做）：

• 在 $s$ 的任意位置插入 $t$（得到一个新的 $s$）。

请你告诉青山，是否有可能通过若干次操作使 $s$ 变成“好”的。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（$1\le T\le 2000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 50$），分别表示字符串 $s$ 和 $t$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$。

第三行包含一个长度为 $m$ 的字符串 $t$。

保证 $s$ 和 $t$ 只包含 $\texttt{0}$ 和 $\texttt{1}$。

输出格式

对于每个测试用例，如果有可能将 $s$ 变成“好”的，输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

输出字母大小写均可。

说明/提示

在第一个测试用例中，$s$ 本身就是“好”的，因此可以不进行任何操作。

在第二个测试用例中，你可以进行如下两次操作（插入的字符串 $t$ 用下划线表示）：

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

最终得到 $s = \texttt{101010101}$，这是一个“好”的字符串。

在第三个测试用例中，无论进行多少次操作，都无法使 $s$ 变成“好”的字符串。

由 ChatGPT 4.1 翻译

样例

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