← 返回题目列表

Codeforces · 2029/B

B. 更换

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

您有一个长度为 $$$n$$$ 的二进制字符串$$$^{\text{∗}}$$$ $$$s$$$,Iris 为您提供了另一个长度为 $$$n-1$$$ 的二进制字符串 $$$r$$$。

Iris 要和你玩一个游戏。游戏过程中,您将对$$$s$$$执行$$$n-1$$$操作。在第 $$$i$$$ 操作中 ($$$1 \le i \le n-1$$$):

- 首先,选择一个索引 $$$k$$$ 使得 $$$1\le k\le |s| - 1$$$ 和 $$$s_{k} \neq s_{k+1}$$$。如果不可能选择这样的指数,你就输了;
- 然后,将 $$$s_ks_{k+1}$$$ 替换为 $$$r_i$$$。请注意,这会将 $$$s$$$ 的长度减少 $$$1$$$。

如果所有 $$$n-1$$$ 操作均成功执行,则您获胜。

确定你是否有可能赢得这场比赛。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^5$$$) — $$$s$$$ 的长度。

第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i=\mathtt{0}$$$ 或 $$$\mathtt{1}$$$)。

第三行包含长度为 $$$n-1$$$ 的二进制字符串 $$$r$$$ ($$$r_i=\mathtt{0}$$$ 或 $$$\mathtt{1}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果您可以赢得游戏,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

6
2
11
0
2
01
1
4
1101
001
6
111110
10000
6
010010
11010
8
10010010
0010010

输出 #1

NO
YES
YES
NO
YES
NO

注意

在第一个测试用例中,您无法执行第一个操作。这样,你就输掉了比赛。

在第二个测试用例中,您可以在唯一操作中选择 $$$k=1$$$,之后 $$$s$$$ 就等于 $$$\mathtt{1}$$$。这样,你就赢得了比赛。

在第三个测试用例中,您可以执行以下操作: $$$\mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1}$$$。