← 返回题目列表

Codeforces · 1890/B

B. 青山爱弦

中文机器翻译题面 查看原题

Qingshan 有一个字符串 $$$s$$$,而 Daniel 有一个字符串 $$$t$$$。这两个字符串仅包含 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$。

长度为 $$$k$$$ 的字符串 $$$a$$$ 是好的当且仅当

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

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

青山想让$$$s$$$变得更好。为此,她可以执行以下操作任意次数(可能为零):

- 将 $$$t$$$ 插入到 $$$s$$$ 的任意位置(获取新的 $$$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”(不带引号)。

您可以以任何大小写(大写或小写)打印字母。

示例

输入 #1

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

输出 #1

Yes
Yes
No
No
No

注意

在第一个测试用例中,$$$s$$$ 最初是好的,所以你可以通过零操作得到一个好的 $$$s$$$。

在第二个测试用例中,可以进行以下两个操作(插入的字符串$$$t$$$带有下划线):

1.$$$\texttt{1}\下划线{\texttt{010}}\texttt{11}$$$
2.$$$\texttt{10101}\下划线{\texttt{010}}\texttt{1}$$$

并得到 $$$s = \texttt{101010101}$$$,这很好。

在第三个测试用例中,无论进行多少次操作都无法使 $$$s$$$ 变得良好。