← 返回题目列表

Codeforces · 1704/A

A. 两个 0-1 序列

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

AquaMoon 有两个二进制序列 $$$a$$$ 和 $$$b$$$,其中仅包含 $$$0$$$ 和 $$$1$$$。 AquaMoon 可以任意多次执行以下两个操作($$$a_1$$$ 是 $$$a$$$ 的第一个元素,$$$a_2$$$ 是 $$$a$$$ 的第二个元素,依此类推):

- 操作1:如果$$$a$$$包含至少两个元素,则将$$$a_2$$$更改为$$$\operatorname{min}(a_1,a_2)$$$,并删除$$$a$$$的第一个元素。
- 操作2:如果$$$a$$$包含至少两个元素,则将$$$a_2$$$更改为$$$\operatorname{max}(a_1,a_2)$$$,并删除$$$a$$$的第一个元素。

请注意,删除$$$a$$$的第一个元素后,原来的$$$a_2$$$成为$$$a$$$的第一个元素,原来的$$$a_3$$$成为$$$a$$$的第二个元素,依此类推,$$$a$$$的长度减少1。

通过使用这些操作确定 AquaMoon 是否可以使 $$$a$$$ 等于 $$$b$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2\,000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 50$$$, $$$m \leq n$$$) — 分别是 $$$a$$$ 和 $$$b$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$a$$$,仅包含$$$0$$$和$$$1$$$。

每个测试用例的第三行包含一个长度为$$$m$$$的字符串$$$b$$$,仅包含$$$0$$$和$$$1$$$。

输出

对于每个测试用例,如果 AquaMoon 可以使用这些选项将 $$$a$$$ 更改为 $$$b$$$,则输出“YES”;否则,输出“NO”。

您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案)。

示例

输入 #1

10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100

输出 #1

YES
YES
NO
NO
NO
YES
YES
NO
NO
YES

注意

在第一个测试用例中,您可以使用操作 2 四次,使 $$$a$$$ 等于 $$$b$$$。

在第二个测试用例中,您可以使用操作 1 四次,使 $$$a$$$ 等于 $$$b$$$。

在第三个测试用例中,可以证明,无论我们如何使用运算,都不可能使$$$a$$$等于$$$b$$$。

在第四个测试用例中,可以证明,无论我们如何使用运算,都不可能使$$$a$$$等于$$$b$$$。

在第五个测试用例中,可以使用操作2三次,使$$$a$$$变为$$$10101$$$,因此$$$a$$$的第一个元素等于$$$b$$$的第一个元素,但可以证明,无论如何操作,$$$a$$$的第二到第五个元素都不可能与$$$b$$$相同。