题目描述

你有一个长度为 $n$ 的二进制字符串 $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_k s_{k+1}$ 替换为 $r_i$。注意，这会使 $s$ 的长度减少 $1$。

如果你能够成功完成所有 $n-1$ 次操作，你就赢了。

请判断你是否有可能赢得这场游戏。

$^{\text{∗}}$ 二进制字符串是指每个字符都是 $0$ 或 $1$ 的字符串。

输入格式

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

每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示 $s$ 的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i=0$ 或 $s_i=1$）。

第三行包含一个长度为 $n-1$ 的二进制字符串 $r$（$r_i=0$ 或 $r_i=1$）。

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

输出格式

对于每组测试用例，如果你能赢得游戏，输出 "YES"（不含引号）；否则输出 "NO"（不含引号）。

你可以用任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。

说明/提示

在第一个测试用例中，你无法进行第一次操作，因此你输了。

在第二个测试用例中，你可以在唯一的一次操作中选择 $k=1$，此后 $s$ 变为 $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}$。

由 ChatGPT 4.1 翻译

样例

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

NO
YES
YES
NO
YES
NO